赣州网站建设jx25,懒人网页编辑器手机版,网站建设如何开票,建材网站建设 南宁二叉树1.二叉树的递归遍历144.二叉树的前序遍历145.二叉树的后序遍历94.二叉树的中序遍历2.二叉树的迭代遍历144.二叉树的前序遍历145.二叉树的后序遍历94.二叉树的中序遍历3.二叉树的层序遍历102.二叉树的层序遍历107.二叉树的层序遍历||199.二叉树的右视图637.二叉树的层平均…
二叉树1.二叉树的递归遍历144.二叉树的前序遍历145.二叉树的后序遍历94.二叉树的中序遍历2.二叉树的迭代遍历144.二叉树的前序遍历145.二叉树的后序遍历94.二叉树的中序遍历3.二叉树的层序遍历102.二叉树的层序遍历107.二叉树的层序遍历||199.二叉树的右视图637.二叉树的层平均值429.N叉树的层序遍历515.在每个树行中找最大值116.填充每个节点的下一个右侧节点指针117.填充每个节点的下一个右侧节点指针||104.二叉树的最大深度111.二叉树的最小深度4.翻转二叉树226.翻转二叉树5.对称二叉树101.对称二叉树572.另一棵树的子树6.二叉树的最大深度104.二叉树的最大深度559.N叉树的最大深度111.二叉树的最小深度7.完全二叉树的节点个数222.完全二叉树的节点个数8.平衡二叉树110.平衡二叉树9.二叉树的所有路径257.二叉树的所有路径10.左叶子之和404.左叶子之和11.找树左下角的值513.找树左下角的值12.路径总和112.路径总和113.路径总和||13.从中序与后序遍历序列构造二叉树106.从中序与后序遍历序列构造二叉树105.从前序与中序遍历序列构造二叉树14.最大二叉树654.最大二叉树15.合并二叉树617.合并二叉树16.二叉搜索树中的搜索700.二叉搜索树中的搜索17.验证二叉搜索树98.验证二叉搜索树18.二叉搜索树的最小绝对差530.二叉搜索树的最小绝对差19.二叉搜索树中的众数501.二叉搜索树中的众数20.二叉树的最近公共祖先236.二叉树的最近公共祖先21.二叉搜索树的最近公共祖先235.二叉搜索树的最近公共祖先22.二叉搜索树中的插入操作701.二叉搜索树中的插入操作23.删除二叉搜索树中的节点450.删除二叉搜索树中的节点24.修剪二叉搜索树669.修剪二叉搜索树25.将有序数组转换为二叉搜索树33.把二叉树转换为累加树538.把二叉搜索树转换为累加树1.二叉树的递归遍历
144.二叉树的前序遍历 思路 前序遍历的顺序是根节点左孩子右孩子 终止条件是当前节点为空。
class Solution {public ListInteger preorderTraversal(TreeNode root) {ListInteger resultnew ArrayListInteger();preorder(root,result);return result;}public void preorder(TreeNode root,ListInteger result) {if(rootnull) {return ;}result.add(root.val);preorder(root.left,result);preorder(root.right,result);}
}145.二叉树的后序遍历 思路 后续遍历就是最后遍历根节点。递归函数里传入左孩子和右孩子即可。 public ListInteger postorderTraversal(TreeNode root) {ListInteger resultnew ArrayListInteger();postorder(root, result);return result;}public void postorder(TreeNode root,ListInteger result) {if(rootnull) {return ;}postorder(root.left,result);postorder(root.right,result);result.add(root.val);}94.二叉树的中序遍历 思路 二叉树的中序遍历就是在中间遍历根节点。
class Solution {public ListInteger inorderTraversal(TreeNode root) {ListInteger resultnew ArrayListInteger();inorder(root, result);return result;}public void inorder(TreeNode root,ListInteger result) {if(rootnull) {return ;}inorder(root.left,result);result.add(root.val);inorder(root.right,result);}
}2.二叉树的迭代遍历
144.二叉树的前序遍历 思路 因为递归都是通过栈来实现的所以我们这里也用栈来实现。 先序遍历的顺序是 中左右。 所以我们先让根节点进去然后操作这个node节点让它弹出来。然后再让右子节点进去这样它就会后出来。这样一步步来处理。 public ListInteger preorderTraversal(TreeNode root) {ListInteger resultnew ArrayList();StackTreeNode stacknew Stack();if(rootnull) {return result;}//先在栈中放入根节点stack.push(root);//当栈不为空时while(!stack.isEmpty()) {TreeNode nodestack.pop();result.add(node.val);//先放右节点因为先进的会压在栈底if(node.right!null) {stack.push(node.right);}if(node.left!null) {stack.push(node.left);}}return result;}145.二叉树的后序遍历 思路 后续遍历的顺序是左右中 所以可以通过先序遍历的代码迭代改一下。 因为进栈的顺序是中左右进入result的顺序就是中右左所以再逆转result数组就可以实现左右中。
94.二叉树的中序遍历 思路 因为加入栈的节点和要处理的节点不一样所以我们用一个指针来控制。 让指针一直遍历左节点然后把遍历过的节点加入栈。 当节点是空的时候栈中弹出元素并且操作这个元素。让指针指向右节点看他有没有孩子。
public ListInteger inorderTraversal(TreeNode root) {ListInteger resultnew ArrayList();StackTreeNode stacknew Stack();if(rootnull) {return result;}TreeNode curroot;while(cur!null||!stack.isEmpty()) {if(cur!null) {//找到最左边的节点把遍历过的节点加入栈中stack.push(cur);curcur.left;}else {curstack.pop();result.add(cur.val);curcur.right;}}return result;}3.二叉树的层序遍历
102.二叉树的层序遍历 思路 层序遍历用队列这中数据结构来实现先将根节点放入队列中记录此时层数的值。然后弹出一个节点时把这个节点的左右孩子加入到队列中。层数的元素个数来判断进入每层的节点。
class Solution {public ListListInteger levelOrder(TreeNode root) {DequeTreeNode dequenew LinkedListTreeNode();ListListInteger resultnew ArrayListListInteger();if(root!null) {deque.offer(root);}while(!deque.isEmpty()) {ListInteger indexnew ArrayListInteger();//用来记录每一层的元素int lendeque.size();//len用来记录每一层的元素个数while(len--0) {TreeNode node deque.poll();index.add(node.val);if(node.left!null) {deque.add(node.left);}if(node.right!null) {deque.add(node.right);}}result.add(index);}return result;}
}107.二叉树的层序遍历|| 思路 将正序遍历的结果逆转一下就行。
class Solution {public ListListInteger levelOrderBottom(TreeNode root) {DequeTreeNode dequenew LinkedListTreeNode();ListListInteger resultnew ArrayListListInteger();if(root!null) {deque.offer(root);}while(!deque.isEmpty()) {ListInteger indexnew ArrayListInteger();//用来记录每一层的元素int lendeque.size();//len用来记录每一层的元素个数while(len--0) {TreeNode node deque.poll();index.add(node.val);if(node.left!null) {deque.add(node.left);}if(node.right!null) {deque.add(node.right);}}result.add(index);}Collections.reverse(result);return result;}
}199.二叉树的右视图 思路 和前边一样一次遍历每个节点当遍历到最后一个节点时再把这个节点加入到结果中。
public ListInteger rightSideView(TreeNode root) {DequeTreeNode dequenew LinkedListTreeNode();ListInteger resultnew ArrayListInteger();if(root!null) {deque.offer(root);}while(!deque.isEmpty()) {int lendeque.size();//len用来记录每一层的元素个数while(len--0) {TreeNode node deque.poll();if(node.left!null) {deque.add(node.left);}if(node.right!null) {deque.add(node.right);}if(len1) {result.add(node.val);}}}return result;}637.二叉树的层平均值
思路 将每层二叉树的和除以每层二叉树的元素个数即可。
class Solution {public ListDouble averageOfLevels(TreeNode root) {DequeTreeNode dequenew LinkedListTreeNode();ListDouble resultnew ArrayListDouble();if(root!null) {deque.offer(root);}while(!deque.isEmpty()) {ListInteger indexnew ArrayListInteger();//用来记录每一层的元素Double sum0.0;int lendeque.size();//len用来记录每一层的元素个数int levelsizedeque.size();while(len--0) {TreeNode node deque.poll();index.add(node.val);if(node.left!null) {deque.add(node.left);}if(node.right!null) {deque.add(node.right);}index.add(node.val);sumnode.val;}result.add(sum/levelsize);}return result;}
}429.N叉树的层序遍历 思路 把以前的左右孩子节点换成一个数组来遍历当遇到空节点时就算停止。 public ListListInteger levelOrder(Node root) {DequeNode dequenew LinkedListNode();ListListInteger resultnew ArrayListListInteger();if(root!null) {deque.offer(root);}while(!deque.isEmpty()) {ListInteger indexnew ArrayListInteger();//用来记录每一层的元素int lendeque.size();//len用来记录每一层的元素个数while(len--0) {Node node deque.poll();index.add(node.val);ListNode childernnode.children;for(Node node1:childern) {if(node1!null) {deque.add(node1);}}}result.add(index);}return result;}515.在每个树行中找最大值 思路 注意此时的max值要用Integer.MIN_VALUE来设置因为可能出现比0小的情况。 public ListInteger largestValues(TreeNode root) {DequeTreeNode dequenew LinkedListTreeNode();ListInteger resultnew ArrayListInteger();if(root!null) {deque.offer(root);}while(!deque.isEmpty()) {int lendeque.size();//len用来记录每一层的元素个数int maxInteger.MIN_VALUE;while(len--0) {TreeNode node deque.poll();maxnode.valmax?node.val:max;if(node.left!null) {deque.add(node.left);}if(node.right!null) {deque.add(node.right);}}result.add(max);}return result;}116.填充每个节点的下一个右侧节点指针 思路 遍历每一层的时候先保留第一个节点然后将这个top指针保留住每次更新下一个节点就行。 public ListListInteger levelOrder(Node root) {DequeNode dequenew LinkedListNode();ListListInteger resultnew ArrayListListInteger();if(root!null) {deque.offer(root);}while(!deque.isEmpty()) {ListInteger indexnew ArrayListInteger();//用来记录每一层的元素int lendeque.size();//len用来记录每一层的元素个数while(len--0) {Node node deque.poll();index.add(node.val);ListNode childernnode.children;for(Node node1:childern) {if(node1!null) {deque.add(node1);}}}result.add(index);}return result;}117.填充每个节点的下一个右侧节点指针|| 思路 和上边没有任何差别思路一样。 public Node connect(Node root) {DequeNode dequenew LinkedListNode();ListInteger resultnew ArrayListInteger();if(root!null) {deque.offer(root);}while(!deque.isEmpty()) {int lendeque.size();//len用来记录每一层的元素个数Node topdeque.pop();//将每层的头节点记录下来if(top.left!null) {deque.add(top.left);}if(top.right!null) {deque.add(top.right);}while(len--1) {Node next deque.poll();if(next.left!null) {deque.add(next.left);}if(next.right!null) {deque.add(next.right);}top.nextnext;//将top节点指向下一个节点topnext;//自己变成top节点}}return root;}104.二叉树的最大深度 思路:每层遍历了多少个就是一共有几层。 public int maxDepth(TreeNode root) {DequeTreeNode dequenew LinkedListTreeNode();ListInteger resultnew ArrayListInteger();if(root!null) {deque.offer(root);}int dept0;while(!deque.isEmpty()) {dept;int lendeque.size();//len用来记录每一层的元素个数int maxInteger.MIN_VALUE;while(len--0) {TreeNode node deque.poll();maxnode.valmax?node.val:max;if(node.left!null) {deque.add(node.left);}if(node.right!null) {deque.add(node.right);}}result.add(max);}return dept;}111.二叉树的最小深度 思路 当节点的左右节点都为空时就代表这个节点为空了。
class Solution {public int minDepth(TreeNode root) {DequeTreeNode dequenew LinkedListTreeNode();ListInteger resultnew ArrayListInteger();if(root!null) {deque.offer(root);}int dept0;while(!deque.isEmpty()) {dept;int lendeque.size();//len用来记录每一层的元素个数while(len--0) {TreeNode node deque.poll();if(node.left!null) {deque.add(node.left);}if(node.right!null) {deque.add(node.right);}if(node.leftnullnode.rightnull) {return dept;}}}return dept;}
}4.翻转二叉树
226.翻转二叉树 思路 判断终止条件结束条件就行函数体中是翻转两个节点的左右孩子可以先序遍历也可以后序遍历。中序遍历则不行。
class Solution {public TreeNode invertTree(TreeNode root) {if(rootnull) {return null;}invertTree(root.left);invertTree(root.right);swap(root);return root;}public void swap(TreeNode root) {TreeNode temproot.left;root.leftroot.right;root.righttemp;}}5.对称二叉树
101.对称二叉树 思路 用递归的方式来进行比较比较根节点的左右两个子树判断出终止条件当两边的值或者有一方为空节点时都返回false。 运用后序遍历法先比较外侧节点再比较内侧节点。最后比较中间节点。
class Solution {public boolean isSymmetric(TreeNode root) {return compare(root.left,root.right);}public boolean compare(TreeNode left,TreeNode right) {if(leftnullright!null) {return false;}else if(left!nullrightnull) {return false;}else if(leftnullrightnull) {return true;}else if(left.val!right.val) {return false;}boolean outSidecompare(left.left,right.right);boolean inSidecompare(left.right,right.left);return outSideinSide;}
}572.另一棵树的子树 思路 运用递归法判断要判断好终止条件然后写出比较两个子树是否一样的函数。判断这棵树和比较的树是否一样或者这颗树的左右子树和比较的树是否一样。这三个条件满足其中一个即可。
class Solution {public boolean compare(TreeNode left,TreeNode right) {if(leftnullright!null) {return false;}else if(left!nullrightnull) {return false;}else if(leftnullrightnull) {return true;}else if(left.val!right.val) {return false;}boolean outSidecompare(left.left,right.left);boolean inSidecompare(left.right,right.right);return outSideinSide;}public boolean isSubtree(TreeNode root, TreeNode subRoot) {if(subRootnull) {return true;}if(rootnull) {return false;}return isSubtree(root.left,subRoot)||isSubtree(root.right,subRoot)||compare(root,subRoot);}
}6.二叉树的最大深度
104.二叉树的最大深度 思路 深度是从根节点往下属。而高度则是从下往上数。 所以深度是先序遍历中左右。 高度是后序遍历左右中。 这里我们求出了根节点的高度也就求出了二叉树的深度。 public int maxDepth(TreeNode root) {if(rootnull) {return 0;}return 1Math.max(maxDepth(root.left), maxDepth(root.right));}559.N叉树的最大深度 思路 递归思路当遇到空节点时深度为0。 然后每一次的最大节点就是当前层的孩子的最大节点。 最后return 1max(children)。 public int maxDepth(Node root) {if(rootnull) {return 0;}ListNode childrenroot.children;int max0;for(Node node:children) {maxMath.max(max,maxDepth(node));}return 1max;}111.二叉树的最小深度 思路 这里的最小深度是一个节点的子树的最小深度如果一个节点还有左节点或者右节点那么此时它就不能称为一个最小节点。因为它有叶子节点就不能称为一个叶子。所以判断条件上要分别判断左子树为空右子树不为空或左子树不为空右子树为空或者左右子树都不为空的情况。
class Solution {public int minDepth(TreeNode root) {if(rootnull) {return 0;}int leftDepthminDepth(root.left);int rightDepthminDepth(root.right);if(root.leftnullroot.right!null) {return 1rightDepth;}if(root.left!nullroot.rightnull) {return 1leftDepth;}return 1Math.min(leftDepth, rightDepth);}
}7.完全二叉树的节点个数
222.完全二叉树的节点个数 思路 普通解法运动递归。
class Solution {public int countNodes(TreeNode root) {if(rootnull) {return 0;}return countNodes(root.left)countNodes(root.right)1;}
}公式解法 完全二叉树的满二叉树节点个数是2^n-1。 所以这时候当遇到的节点是满二叉树时直接用公式求解。 public int countNodes(TreeNode root) {if(rootnull) {return 0;}TreeNode leftroot.left;TreeNode rightroot.right;int leftDept0;int rightDept0;while(left!null) {leftleft.left;leftDept;}while(right!null) {rightright.right;rightDept;}if(leftDeptrightDept) {return (2leftDept)-1;}return countNodes(root.left)countNodes(root.right)1;}8.平衡二叉树
110.平衡二叉树 思路 判断左右子树的高度。判断左子树是不是平衡二叉树如果不是返回-1. 判断右子树是不是平衡二叉树如果不是返回-1. 如果两棵子树的高度差超过1直接返回-1.
class Solution {public boolean isBalanced(TreeNode root) {if(depth(root)-1) {return false;}return true;}public int depth(TreeNode root) {if(rootnull) {return 0;}//求左子树的高度int leftdepthdepth(root.left);if(leftdepth-1) {return -1;}int rightdepthdepth(root.right);if(rightdepth-1) {return -1;}int result;if(Math.abs(leftdepth-rightdepth)1) {return -1;}else {return 1Math.max(leftdepth, rightdepth);} }
}9.二叉树的所有路径
257.二叉树的所有路径 思路 递归法先序遍历中左右。 每次碰到一个节点把它放入路径中。 如果这个是叶子节点就可以输入了。 如果不是叶子节点就继续去递归递归完之后把最后一个元素弄出来。这就是回溯法。
class Solution {public ListString binaryTreePaths(TreeNode root) {ListString resultnew ArrayListString();if(rootnull) {return result;}ListInteger pathsnew ArrayListInteger();traversal(root,paths,result);return result;}public void traversal(TreeNode root,ListIntegerpaths,ListString result) {paths.add(root.val);//如果遇到了叶子节点就要考虑输出了。if(root.leftnullroot.rightnull) {StringBuilder pathnew StringBuilder();for(int i0;ipaths.size()-1;i) {path.append(paths.get(i)).append(-);}path.append(paths.get(paths.size()-1));result.add(path.toString());return ;}//如果左节点不为空if(root.left!null) {traversal(root.left,paths,result);//进行回溯操作把最后一个节点弹出去paths.remove(paths.size()-1);}//如果右节点不为空if(root.right!null) {traversal(root.right,paths,result);paths.remove(paths.size()-1);}}}10.左叶子之和
404.左叶子之和 思路
如果遇到空节点返回null。 总和是左子树的左节点之和加上右子树的左节点之和。 判断左节点时要从它的父节点找当父节点有左节点时并且左节点没有左右孩子节点。就可以了。
class Solution {public int sumOfLeftLeaves(TreeNode root) {if(rootnull) {return 0;}int leftSumsumOfLeftLeaves(root.left);int rightSumsumOfLeftLeaves(root.right);int middle0;if(root.left!nullroot.left.leftnullroot.left.rightnull) {middleroot.left.val;}return middleleftSumrightSum;}
}11.找树左下角的值
513.找树左下角的值 思路 用迭代法比较简单。 这里使用递归法。用一个额外变量记录最大深度。用额外变量记录result。当找到叶子节点时判断此时是不是最大深度如果是更新value值因为是先进行左节点遍历所以会先找到最大层数的左节点。
class Solution {private int Deep -1;private int value 0;public int findBottomLeftValue(TreeNode root) {valueroot.val;findLeftValue(root,0);return value;}public void findLeftValue(TreeNode root,int dept) {if(rootnull) {return ;}//找到叶子节点if(root.leftnullroot.rightnull) {if(deptDeep) {Deepdept;valueroot.val;}}//先找左节点if(root.left!null) {dept;findLeftValue(root.left,dept);dept--;//用到了回溯找完左节点再退回去找右节点}if(root.right!null) {dept;findLeftValue(root.right,dept);dept--;}}
}12.路径总和
112.路径总和 思路 这道题只是判断有没有对应的路径满足条件所以不需要做输出处理。 当遍历到一个节点时需要减去这个节点的值最后当遍历到叶子节点时判断数值是不是0即可。
public boolean hasPathSum(TreeNode root, int targetSum) {if(rootnull) {return false;}//当弹出去的时候就相当于了回溯的过程targetSum-root.val;if(root.leftnullroot.rightnull) {return targetSum0;}if(root.left!null) {boolean lefthasPathSum(root.left,targetSum);//当判断左子树满足条件时才会直接返回true所以当是false的时候不会直接终止函数if(left) {return true;}}if(root.right!null) {boolean righthasPathSum(root.right,targetSum);if(right) {return true;}}return false;}
113.路径总和|| 思路 把所有的路径都遍历一遍就是不需要返回值把结果数组放入res里面即可。注意要有回溯操作。
public ListListInteger pathSum(TreeNode root, int targetSum) {ListListInteger resnew ArrayList();if(rootnull) return res;ListInteger pathnew LinkedList();preorderdfs(root,targetSum,res,path);return res;}public void preorderdfs(TreeNode root, int targetsum, ListListInteger res, ListInteger path) {path.add(root.val);//遇到了叶子节点if(root.leftnullroot.rightnull) {//找到了和为targetSum的路径if(targetsum-root.val0) {res.add(new ArrayList(path));}return ;}if(root.left!null) {preorderdfs(root.left, targetsum-root.val, res, path);//回溯path.remove(path.size()-1);}if(root.right!null) {preorderdfs(root.right,targetsum-root.val,res,path);path.remove(path.size()-1);}}13.从中序与后序遍历序列构造二叉树
106.从中序与后序遍历序列构造二叉树 思路 1.找到后序遍历的最后一个节点就是根节点。 2.根据根节点去切割中序遍历可以找到左子树和右子树的范围。 3.根据中序遍历中左子树和右子树的范围可以找到后序遍历中的左子树和右子树。 4.然后再进行递归求解中序遍历的左子树和后序遍历的左子树这又是一个新的条件。所以可以继续求解。 MapInteger,Integer map;public TreeNode buildTree(int[] inorder, int[] postorder) {mapnew HashMap();for(int i0;iinorder.length;i) {//用map保存中序序列的数值对应位置map.put(inorder[i], i);}return findNode(inorder,0,inorder.length,postorder,0,postorder.length);}public TreeNode findNode(int[] inorder, int inBegin, int inEnd, int[] postorder, int postBegin, int postEnd) {if(inBegininEnd||postBeginpostEnd) {return null;}//找到中序遍历中根节点的位置int rootIndexmap.get(postorder[postEnd-1]);TreeNode rootnew TreeNode(inorder[rootIndex]);//根据根节点的位置确定中序遍历总左子树的数量int lengthofLeftrootIndex-inBegin;root.leftfindNode(inorder,inBegin,rootIndex,postorder,postBegin,postBeginlengthofLeft);//左子树分别在中序和后序的位置root.rightfindNode(inorder,rootIndex1,inEnd,postorder,postBeginlengthofLeft,postEnd-1);//右子树分别在中序和后序的位置return root;}105.从前序与中序遍历序列构造二叉树 思路 和后序中序生成二叉树一样。 依靠先序第一个节点找到根节点。然后再根据根节点在中序上找找到位置就可以分出左子树和右子树。 这样两种遍历方式的左右子树都分出来了。最后就递归生成即可。
MapInteger,Integermap;public TreeNode buildTree(int[] preorder, int[] inorder) {mapnew HashMap();//把中序遍历中每个元素出现的位置存起来for(int i0;iinorder.length;i) {map.put(inorder[i],i);}return findNode(preorder,0,preorder.length,inorder,0,inorder.length);}public TreeNode findNode(int[] preorder,int preBegin,int preEnd,int[] inorder, int inBegin, int inEnd) {//参数范围都是前闭后开if(preBeginpreEnd||inBegininEnd) {return null;}int rootIndexmap.get(preorder[preBegin]);//找到根节点在中序遍历的位置TreeNode rootnew TreeNode(inorder[rootIndex]);//找到左子树的数量int lengthOfLeftrootIndex-inBegin;root.leftfindNode(preorder,preBegin1,preBegin1lengthOfLeft,inorder,inBegin,inBeginlengthOfLeft);root.rightfindNode(preorder,preBegin1lengthOfLeft,preEnd,inorder,rootIndex1,inEnd);return root;}14.最大二叉树
654.最大二叉树 思路 递归函数里要确定终止条件。 1.当区间里没有元素时直接返回null。 2.当区间里只有一个元素时直接构造一个节点。 3.找到这个区间里的最大值和最大元素下标。 4.用最大值创建一个节点。根据最大元素下标去切分剩下的数组。来生成左子树和右子树。 public TreeNode constructMaximumBinaryTree(int[] nums) {return constructMaximumBinaryTree1(nums,0,nums.length);}public TreeNode constructMaximumBinaryTree1(int[] nums,int leftIndex,int rightIndex) {//判断终止条件如果区间里边没有元素了直接返回if(leftIndexrightIndex) {return null;}//如果区间里边只有一个元素那么直接返回这个节点if((rightIndex-leftIndex)1) {return new TreeNode(nums[leftIndex]);}//找到区间里最大的元素和下标。找最大的元素构造根节点找到下标用来切分数组int maxValuenums[leftIndex];int maxIndexleftIndex;for(int ileftIndex1;irightIndex;i) {if(nums[i]maxValue) {maxValuenums[i];maxIndexi;}}//用这个最大的元素来构造根节点TreeNode rootnew TreeNode(maxValue);//递归去找左子树root.leftconstructMaximumBinaryTree1(nums,leftIndex,maxIndex);root.rightconstructMaximumBinaryTree1(nums,maxIndex1,rightIndex);return root;}
15.合并二叉树
617.合并二叉树 思路 用递归来做当左子树是空时返回右子树。 当右子树是空时返回左子树。 然后合并之后的树等于左子树和右子树两个数的继续合并。 public TreeNode mergeTrees(TreeNode root1, TreeNode root2) {if(root1null) {return root2;}if(root2null) {return root1;}root1.valroot2.val;root1.leftmergeTrees(root1.left,root2.left);root1.rightmergeTrees(root1.right,root2.right);return root1;}16.二叉搜索树中的搜索
700.二叉搜索树中的搜索 思路 终止条件当遇到的节点是空时或者遇到的节点的值等于目标值时返回这个节点。 根据二叉搜索树的特点 递归里的逻辑当节点的值比目标值小时向右子树查找。当节点的值比目标值大时向左子树查找。 public TreeNode searchBST(TreeNode root, int val) {//终止条件if(rootnull||root.valval) {return root;}//递归里的逻辑TreeNode nodenull;if(root.valval) {nodesearchBST(root.left,val);}else if(root.valval) {nodesearchBST(root.right,val);}return node;}
17.验证二叉搜索树
98.验证二叉搜索树 思路 用一个指针去记录左边的节点当这个节点不等于null并且数值大于等于中间的节点的时候就判断出了它不是二叉搜索树。返回false。 public TreeNode pre;public boolean isValidBST(TreeNode root) {//当节点为空的时候if(rootnull) {return true;}//判断左边是不是二叉搜索树boolean leftisValidBST(root.left);if(!left) {return false; }//判断中间是不是二叉搜索树if(pre!nullpre.valroot.val) {return false;}preroot;boolean rightisValidBST(root.right);return leftright;}18.二叉搜索树的最小绝对差
530.二叉搜索树的最小绝对差 思路 定义两个指针一个前指针一个后指针两个指针一步一步的走采用中序遍历的方式如果一步一步的走将每次最小的差值记录下来。
class Solution {public int resultInteger.MAX_VALUE;TreeNode pre1;public int getMinimumDifference(TreeNode root) {if(rootnull) return 0;traversal(root);return result;}public void traversal(TreeNode root) {if(rootnull) {return ;}//采用中序遍历traversal(root.left);if(pre1!null) {result(root.val-pre1.val)result?(root.val-pre1.val):result;}pre1root;traversal(root.right);}
}19.二叉搜索树中的众数
501.二叉搜索树中的众数 思路 有一个maxcount变量来记录出现最大的次数。count记录当前数字出现的数。如果前指针和后指针不相等时count等于1代表出现一次。然后每次相等的时候count。 当countmaxcount的时候把结果更新进去如果count大于maxcount了只需要清空结果集里的元素然后把后面的元素加进去即可。 ListInteger resnew ArrayListInteger();int maxCount0;int count0;TreeNode pre2null;public int[] findMode(TreeNode root) {if(rootnull) {return res.stream().mapToInt(x-x).toArray() ;}findMode(root.left);if(prenull||root.val!pre.val) {count1;}else {count;}//更新结果以及maxCountif(countmaxCount) {res.clear();res.add(root.val);maxCountcount;}else if(countmaxCount) {res.add(root.val);}preroot;findMode(root.right);return res.stream().mapToInt(x-x).toArray() ;}20.二叉树的最近公共祖先
236.二叉树的最近公共祖先 思路 终止条件当节点为空时或者左节点找到了目标节点或者右节点找到了目标节点。 采用后序遍历的方法。 先看左子树有没有目标值再看右子树有没有目标值。 如果左子树和右子树都有了目标值直接返回root。 如果两个子树中仅有一个有目标值返回这个子树即可。 public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {if(rootnull||rootp||rootq) {//递归条件结束,当有一个节点找到p或q时递归结束return root;}//采用后序遍历TreeNode leftlowestCommonAncestor(root.left,p,q);TreeNode rightlowestCommonAncestor(root.right,p,q);//当两个节点都没找到时if(leftnullrightnull) {return null;}else if(leftnullright!null) {//当右节点找到一个目标值时,左节点没有找到返回右节点return right;}else if(left!nullrightnull) {//当左节点找到一个目标值时右节点没有找到,返回左节点return left;}else {return root;//当两个节点都找到了目标值直接返回root}}21.二叉搜索树的最近公共祖先
235.二叉搜索树的最近公共祖先 思路 当根节点为空时返回null。 当根节点的数值大于目标节点的数值时。往左子树查找如果左子树不为空直接返回左子树即可。 当根节点的数值小于目标节点的数值时。往右子树查找如果右子树不为空直接返回右子树即可。 如果根节点的数值在两个节点之间。那么返回这个节点即可。 public TreeNode lowestCommonAncestor2(TreeNode root, TreeNode p, TreeNode q) {//二叉搜索树因为知道了节点大小所以搜索起来会方便很多。if(rootnull) {return null;}if(root.valp.valroot.valq.val) {//说明根节点的数值比两个目标值大所以结果在左边TreeNode leftlowestCommonAncestor2(root.left,p,q);if(left!null) {//如果左节点不等于null直接返回即可return left;}}if(root.valp.valroot.valq.val) {//说明根节点的数值比两个目标值小所以结果在右边TreeNode rightlowestCommonAncestor2(root.right,p,q);if(right!null) {//如果右节点不等于null直接返回即可。return right;}}return root;}22.二叉搜索树中的插入操作
701.二叉搜索树中的插入操作
思路用递归法当遇到空节点时直接生成节点然后返回这个节点。这样递归函数返回到上一层时让左子树的节点指向这个节点。 public TreeNode insertIntoBST(TreeNode root, int val) {//当遇到的节点为空时构造新的节点if(rootnull) {TreeNode childrennew TreeNode(val);return children;}//如果节点的值比目标值大往左子树去插if(root.valval) {root.leftinsertIntoBST(root.left,val);}//如果节点的值比目标值小往右子树去插if(root.valval) {root.rightinsertIntoBST(root.right,val);}return root;}23.删除二叉搜索树中的节点
450.删除二叉搜索树中的节点 思路 把5种情况理清楚就可以了。
public TreeNode deleteNode(TreeNode root, int key) {/*** 分为五种情况key没有找到* 删除叶子节点* 删除节点有左子树直接让它指向左子树即可* 删除节点有右子树直接让它指向右子树即可* 删除节点左右子树都有找到右子树的最小节点的值然后让这个子树的左节点指向它即可。*/if(rootnull) {return null;}if(root.valkey) {//找到了节点if(root.leftnullroot.rightnull) {//删除叶子节点return null;}else if(root.left!nullroot.rightnull) {//删除节点有左子树return root.left;}else if(root.leftnullroot.right!null) {//删除节点有右子树return root.right;}else {TreeNode curroot.right;//找到右子树的最左边的节点while(cur.left!null) {curcur.left;}cur.leftroot.left;return root.right;}}//告诉节点规则让它在哪个方向去找Keyif(root.valkey) {root.leftdeleteNode(root.left,key);}else if(root.valkey) {root.rightdeleteNode(root.right,key);}return root;}24.修剪二叉搜索树
669.修剪二叉搜索树 思路 当修剪到叶子节点时节点比左边界要小返回这个节点修剪后的右子树给上一个节点。节点比右边界要大返回这个节点修剪后的左子树给上一个节点。如果这个节点恰好在两个中间那么直接返回这个节点即可。 public TreeNode trimBST(TreeNode root, int low, int high) {//当遇到空节点返回nullif(rootnull) {return null;}//当遇见的节点比左边界的值要小让右子树去剪枝返回右子树if(root.vallow) {TreeNode righttrimBST(root.right,low,high);return right;}//当遇见的节点比右边界的值要大让左子树去剪枝返回左子树if(root.valhigh) {TreeNode lefttrimBST(root.left,low,high);return left;}//当遇见的节点在两个边界点之间。分别对左右两个子树减枝即可root.lefttrimBST(root.left,low,high);root.righttrimBST(root.right,low,high);return root;}25.将有序数组转换为二叉搜索树 思路 用递归的方式找到中间节点然后生成这个节点递归去遍历左右区间。 public TreeNode sortedArrayToBST(int[] nums) {return sortedArray(nums,0,nums.length-1);}public TreeNode sortedArray(int[]nums,int left,int right) {//运用中节点递归去处理,采用左闭右闭区间if(leftright) {return null;}int mid(leftright)/2;TreeNode rootnew TreeNode(nums[mid]);root.leftsortedArray(nums,left,mid-1);root.rightsortedArray(nums,mid1,right);return root;}33.把二叉树转换为累加树
538.把二叉搜索树转换为累加树 思路 用右中左的顺序去遍历把前一个节点的值记录好然后顺序更新即可。 int pre30;public TreeNode convertBST(TreeNode root) {//右中左的顺序去遍历然后每次更新pre的树枝即可.if(rootnull) {return null;}convertBST(root.right);//中间节点的逻辑root.valpre3;pre3root.val;convertBST(root.left);return root;}
