长沙做医院的网站建设,2017网站开发合同下载,wordpress自带图片,所有网站排名2015年文章目录 二叉树的遍历方式深度优先遍历广度优先遍历 二叉树属性#xff08;一般后序遍历求解#xff09;深度问题节点个数问题其他问题 二叉树的修改与构造#xff08;一般前序遍历求解#xff09;构造二叉树 二叉树与回溯二叉搜索树的属性(一般中序遍历)二叉树公共祖先问… 文章目录 二叉树的遍历方式深度优先遍历广度优先遍历 二叉树属性一般后序遍历求解深度问题节点个数问题其他问题 二叉树的修改与构造一般前序遍历求解构造二叉树 二叉树与回溯二叉搜索树的属性(一般中序遍历)二叉树公共祖先问题二叉搜索树的修改与构造前序总结 二叉树的遍历方式
深度优先遍历
力扣相关题目 144.二叉树的前序遍历 145.二叉树的后序遍历 94.二叉树的中序遍历
递归遍历Java代码
// 前序遍历·递归·LC144_二叉树的前序遍历
class Solution {public ListInteger preorderTraversal(TreeNode root) {ListInteger result new ArrayListInteger();preorder(root, result);return result;}public void preorder(TreeNode root, ListInteger result) {if (root null) {return;}result.add(root.val);preorder(root.left, result);preorder(root.right, result);}
}
// 中序遍历·递归·LC94_二叉树的中序遍历
class Solution {public ListInteger inorderTraversal(TreeNode root) {ListInteger res new ArrayList();inorder(root, res);return res;}void inorder(TreeNode root, ListInteger list) {if (root null) {return;}inorder(root.left, list);list.add(root.val); // 注意这一句inorder(root.right, list);}
}
// 后序遍历·递归·LC145_二叉树的后序遍历
class Solution {public ListInteger postorderTraversal(TreeNode root) {ListInteger res new ArrayList();postorder(root, res);return res;}void postorder(TreeNode root, ListInteger list) {if (root null) {return;}postorder(root.left, list);postorder(root.right, list);list.add(root.val); // 注意这一句}
}迭代遍历Java代码统一
class Solution {// 前序遍历·迭代·LC144_二叉树的前序遍历public ListInteger preorderTraversal(TreeNode root) {ListInteger res new ArrayList();StackTreeNode stack new Stack();if (root ! null) stack.push(root);while(!stack.empty()){TreeNode node stack.peek();if (node ! null){stack.pop();if (node.right ! null) stack.push(node.right);if (node.left ! null) stack.push(node.left);// 待处理节点stack.push(node);stack.push(null);}else{// 在这里处理stack.pop();node stack.peek();stack.pop();res.add(node.val);}}return res;}// 中序遍历·迭代·LC94_二叉树的中序遍历public ListInteger inorderTraversal(TreeNode root) {ListInteger res new ArrayList();StackTreeNode stack new Stack();if (root ! null) stack.push(root);while(!stack.empty()){TreeNode node stack.peek();if (node ! null){stack.pop();if (node.right ! null) stack.push(node.right);// 待处理节点stack.push(node);stack.push(null);if (node.left ! null) stack.push(node.left);}else{stack.pop();node stack.peek();stack.pop();res.add(node.val);}}return res;}// 后序遍历·迭代·LC145_二叉树的后序遍历public ListInteger postorderTraversal(TreeNode root) {ListInteger res new ArrayList();StackTreeNode stack new Stack();if (root ! null) stack.push(root);while(!stack.empty()){TreeNode node stack.peek();if (node ! null){stack.pop();// 待处理节点stack.push(node);stack.push(null);if (node.right ! null) stack.push(node.right);if (node.left ! null) stack.push(node.left);}else{stack.pop();node stack.peek();stack.pop();res.add(node.val);}}return res;}
}广度优先遍历
力扣相关题目 102.二叉树的层序遍历 199.二叉树的右视图 429.N叉树的层序遍历
java代码
class Solution {public ListListInteger res new ArrayList();// 递归法public void level1(TreeNode node, int level){if (node null) return;level;if (res.size() level){ListInteger item new ArrayList();res.add(item);}res.get(level - 1).add(node.val);level1(node.left,level);level1(node.right,level);}// 迭代法public void level2(TreeNode node){if (node null) return;QueueTreeNode q new LinkedList();q.offer(node);while(!q.isEmpty()){ListInteger item new ArrayList();int n q.size();while(n 0){TreeNode tmp q.poll();item.add(tmp.val);if (tmp.left ! null) q.offer(tmp.left);if (tmp.right ! null) q.offer(tmp.right);n --;}res.add(item);}}// 102.二叉树的层序遍历public ListListInteger levelOrder(TreeNode root) {// level2(root);level1(root,0);return res;}// 199.二叉树的右视图public ListInteger rightSideView(TreeNode root) {ListInteger res new ArrayList();QueueTreeNode pq new LinkedList();if (root null) return res;pq.offer(root);while(! pq.isEmpty()){int n pq.size();for (int i 0; i n; i ){TreeNode tmp pq.poll();if (i n - 1) res.add(tmp.val);if (tmp.left ! null) pq.offer(tmp.left);if (tmp.right ! null) pq.offer(tmp.right);}}return res;}// 429.N叉树的层序遍历public ListListInteger levelOrder(Node root) {ListListInteger list new ArrayList();DequeNode que new LinkedList();if (root null) {return list;}que.offerLast(root);while (!que.isEmpty()) {int levelSize que.size();ListInteger levelList new ArrayList();for (int i 0; i levelSize; i) {Node poll que.pollFirst();levelList.add(poll.val);ListNode children poll.children;if (children null || children.size() 0) {continue;}for (Node child : children) {if (child ! null) {que.offerLast(child);}}}list.add(levelList);}return list;}class Node {public int val;public ListNode children;public Node() {}public Node(int _val) {val _val;}public Node(int _val, ListNode _children) {val _val;children _children;}}
}二叉树属性一般后序遍历求解
深度问题
力扣相关题目 104.二叉树的最大深度 111.二叉树的最小深度 110.平衡二叉树 513.找树左下角的值
java代码
class Solution {// 104.二叉树的最大深度// 采用后序遍历回溯public int maxDepth(TreeNode root) {// 终止条件if (root null) {return 0;}// 遍历左节点int leftDepth maxDepth(root.left);// 遍历右节点int rightDepth maxDepth(root.right);// 处理逻辑return Math.max(leftDepth, rightDepth) 1;}// 111.二叉树的最小深度// 最小深度从根节点到最近叶子节点的最短路径上的节点数量。注意是叶子节点。// 所以如果左子树为空右子树不为空说明最小深度是 1 右子树的深度// 反之右子树为空左子树不为空最小深度是 1 左子树的深度。 最后如果左右子树都不为空返回左右子树深度最小值 1 。public int minDepth(TreeNode root) {if (root null) return 0;int left minDepth(root.left);int right minDepth(root.right);if (root.left null root.right ! null) return 1 right;if (root.left ! null root.right null) return 1 left;return 1 Math.min(left,right);}// 110.平衡二叉树// 一棵高度平衡二叉树定义为一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过1// public int getHeight(TreeNode root){if (root null) return 0;int leftheight getHeight(root.left); // 左if (leftheight -1) return -1;int rightheight getHeight(root.right); // 右if (rightheight -1) return -1;// 如果左右子树高度差大于1则赋值-1if (Math.abs(leftheight - rightheight) 1){return -1;} // 如果不是则返回以当前节点为根节点的树的最大高度return Math.max(leftheight,rightheight) 1;}public boolean isBalanced(TreeNode root) {return getHeight(root) ! -1;}// 513.找树左下角的值// 转化为求解二叉树深度问题用到前序遍历int Depth -1;int value 0;public void findLeftvalue(TreeNode root, int depth){if (root null) return;// 找到叶子节点// 前序遍历保证优先左边搜索if (root.left null root.right null){if (depth Depth){value root.val;Depth depth;}}if (root.left ! null) findLeftvalue(root.left, depth 1);if (root.right ! null) findLeftvalue(root.right, depth 1); }public int findBottomLeftValue(TreeNode root) {value root.val;findLeftvalue(root,0);return value;}
}节点个数问题
力扣相关题目 222.完全二叉树的节点个数
java代码
class Solution {// 222.完全二叉树的节点个数// 完全二叉树除了最底层节点可能没填满外其余每层节点数都达到最大值并且最下面一层的节点都集中在该层最左边的若干位置。// 若最底层为第 h 层则该层包含1~ 2^(h-1) 个节点// 完全二叉树只有两种情况情况一就是满二叉树情况二最后一层叶子节点没有满// 对于情况一可以直接用 2^树深度 - 1 来计算注意这里根节点深度为1// 对于情况二分别递归左孩子和右孩子递归到某一深度一定会有左孩子或者右孩子为满二叉树然后依然可以按照情况1来计算。// 如何判断满二叉树// 在完全二叉树中如果递归向左遍历的深度等于递归向右遍历的深度那说明就是满二叉树// 在完全二叉树中如果递归向左遍历的深度不等于递归向右遍历的深度则说明不是满二叉树public int countNodes(TreeNode root) {if (root null) return 0;// 终止条件写法// 开始根据左深度和右深度是否相同来判断该子树是不是满二叉树TreeNode l root.left;TreeNode r root.right;int lcount 0, rcount 0;while(l ! null){lcount ; // 求左子树深度l l.left;}while(r ! null){rcount ; // 求右子树深度r r.right;}if (lcount rcount){return (2 lcount) - 1;}// 后序遍历return countNodes(root.left) countNodes(root.right) 1;}}其他问题
力扣相关题目 101. 对称二叉树 404.左叶子之和
java代码
class Solution {// 101. 对称二叉树public boolean isSymmetric(TreeNode l, TreeNode r){// 首先排除空节点的情况if (l null r null) return true;else if (l ! null r null) return false;else if (l null r ! null) return false;// 排除了空节点再排除数值不相同的情况else if (l.val ! r.val) return false;// 后序遍历return isSymmetric(l.left,r.right) isSymmetric(l.right, r.left);}public boolean isSymmetric(TreeNode root) {if (root null) return false;return isSymmetric(root.left, root.right);}// 404.左叶子之和public int sumOfLeftLeaves(TreeNode root) {if (root null) return 0;int sum 0;int left sumOfLeftLeaves(root.left);int right sumOfLeftLeaves(root.right);int mid 0;if (root.left ! null root.left.left null root.left.right null){mid root.left.val;}sum mid left right;return sum;}}二叉树的修改与构造一般前序遍历求解
力扣相关题目 226.翻转二叉树 654.最大二叉树 617.合并二叉树
java代码
class Solution {// 226.翻转二叉树public TreeNode invertTree(TreeNode root) {if (root null) return null;// 执行操作TreeNode tmp root.left;root.left root.right;root.right tmp;invertTree(root.left); // 左invertTree(root.right); // 右return root;}// 654.最大二叉树public TreeNode constructMaximumBinaryTree(int[] nums, int start, int end){if (end - start 1) return null;if (end - start 1) return new TreeNode(nums[start]);// 最大值所在位置int maxValue nums[start];int maxID start;for (int i start; i end; i ){if (nums[i] maxValue){maxValue nums[i];maxID i;}}TreeNode root new TreeNode(maxValue);// 根据maxIndex划分左右子树root.left constructMaximumBinaryTree(nums,start,maxID);root.right constructMaximumBinaryTree(nums,maxID 1, end);return root;}// 617.合并二叉树public TreeNode constructMaximumBinaryTree(int[] nums) {return constructMaximumBinaryTree(nums,0,nums.length);}public TreeNode mergeTrees(TreeNode root1, TreeNode root2) {if (root1 null) return root2; // 如果root1为空合并之后就应该是root2if (root2 null) return root1;// 以root1为基础root1.val root2.val;root1.left mergeTrees(root1.left,root2.left);root1.right mergeTrees(root1.right,root2.right);return root1;}
}构造二叉树
力扣相关题目 106.从中序与后序遍历序列构造二叉树 105.从前序与中序遍历序列构造二叉树
java代码
class Solution {// 106.从中序与后序遍历序列构造二叉树MapInteger,Integer map;public TreeNode findNode(int[] inorder, int inBegin, int inEnd, int[] postorder, int postBegin, int postEnd){if (inBegin inEnd || postBegin postEnd) return null;int rootIndex map.get(postorder[postEnd - 1]);int leftLen rootIndex - inBegin;TreeNode root new TreeNode(postorder[postEnd - 1]);root.left findNode(inorder,inBegin,rootIndex,postorder,postBegin,postBegin leftLen);root.right findNode(inorder, rootIndex 1, inEnd, postorder, postBegin leftLen, postEnd - 1);return root;}public TreeNode buildTree(int[] inorder, int[] postorder) {map new HashMapInteger,Integer ();for (int i 0; i inorder.length; i ){map.put(inorder[i],i);}return findNode(inorder,0,inorder.length, postorder, 0, postorder.length);}// 105.从前序与中序遍历序列构造二叉树public MapInteger,Integer map;public TreeNode findNode(int[] preorder, int preBegin, int preEnd, int[] inorder, int inBegin, int inEnd){if (preBegin preEnd || inBegin inEnd) return null;int rootIndex map.get(preorder[preBegin]);int leftLen rootIndex - inBegin;TreeNode root new TreeNode(inorder[rootIndex]);root.left findNode(preorder,preBegin 1, preBegin 1 leftLen, inorder, inBegin, rootIndex);root.right findNode(preorder, preBegin 1 leftLen, preEnd, inorder, rootIndex 1,inEnd);return root;}public TreeNode buildTree(int[] preorder, int[] inorder) {map new HashMap();for (int i 0; i inorder.length; i ){map.put(inorder[i],i);}return findNode(preorder, 0, preorder.length, inorder,0,inorder.length);}
}二叉树与回溯
力扣相关题目 257. 二叉树的所有路径 112. 路径总和 113.路径总和ii
java代码
class Solution {// 257. 二叉树的所有路径// 前序遍历// 如果需要搜索整棵二叉树且不用处理递归返回值递归函数就不要返回值public void traveral(TreeNode root, ListInteger path, ListString res){path.add(root.val);if (root.left null root.right null){StringBuffer sb new StringBuffer();for (int i 0; i path.size() - 1; i ){sb.append(path.get(i));sb.append(-);}sb.append(path.get(path.size() - 1));res.add(sb.toString());return;}if (root.left ! null){traveral(root.left,path,res);path.remove(path.size() - 1);}if (root.right ! null){traveral(root.right,path,res);path.remove(path.size() - 1);}}public ListString binaryTreePaths(TreeNode root) {ListString res new ArrayList();ListInteger path new ArrayList();if (root null) return res;traveral(root,path,res);return res;}// 112. 路径总和// 如果要搜索其中一条符合条件的路径那么递归一定需要返回值因为遇到符合条件的路径了就要及时返回public boolean traveral(TreeNode root, int count){if(root.left null root.right null count 0) return true;if(root.left null root.right null) return false;if (root.left ! null){count - root.left.val;if (traveral(root.left,count)) return true;count root.left.val;}if (root.right ! null){count - root.right.val;if (traveral(root.right,count)) return true;count root.right.val;}return false;}public boolean hasPathSum(TreeNode root, int targetSum) {if (root null) return false;return traveral(root,targetSum - root.val);}// 113.路径总和ii// 如果需要搜索整棵二叉树且不用处理递归返回值递归函数就不要返回值public void traversal(TreeNode root, int targetSum, ListInteger path, ListListInteger res){path.add(root.val);if (root.left null root.right null){if (targetSum - root.val 0) res.add(new ArrayList(path));else return;}if (root.left ! null){traversal(root.left,targetSum - root.val,path,res);path.remove(path.size() - 1);}if (root.right ! null){traversal(root.right,targetSum - root.val,path,res);path.remove(path.size() - 1);}}public ListListInteger pathSum(TreeNode root, int targetSum) {ListListInteger res new ArrayList();if (root null) return res;ListInteger path new ArrayList();traversal(root,targetSum,path,res);return res;}}二叉搜索树的属性(一般中序遍历)
力扣相关题目 700.二叉搜索树中的搜索 98.验证二叉搜索树 530.二叉搜索树的最小绝对差 501.二叉搜索树中的众数 538.把二叉搜索树转换为累加树
java代码
class Solution {// 700.二叉搜索树中的搜索public TreeNode searchBST(TreeNode root, int val) {if (root null) return null;if (root.val val) return root;if (val root.val) return searchBST(root.left,val);if (val root.val) return searchBST(root.right,val);return null;}// 98.验证二叉搜索树TreeNode max; // 用于标记上一遍历的节点public boolean isValidBST(TreeNode root) {if (root null) return true;boolean left isValidBST(root.left);if (!left) return false;// 处理逻辑if (max ! null root.val max.val) {return false;}max root;boolean right isValidBST(root.right);return right;}// 530.二叉搜索树的最小绝对差int result Integer.MAX_VALUE;TreeNode pre;public void traversal(TreeNode root){if (root null) return;traversal(root.left);if (pre ! null){result Math.min(result, root.val - pre.val);}pre root;traversal(root.right);}public int getMinimumDifference(TreeNode root) {if (root null) return 0;traversal(root);return result;}// 501.二叉搜索树中的众数ListInteger ans;int maxCount;int count;TreeNode pre;public void traversal(TreeNode root){if (root null) return;traversal(root.left);if (pre null || pre.val ! root.val){count 1;}else{count ;}if (count maxCount){ans.clear();ans.add(root.val);maxCount count;}else if (count maxCount){ans.add(root.val);}pre root;traversal(root.right);}public int[] findMode(TreeNode root) {ans new ArrayList();maxCount 0;count 0;pre null;traversal(root);int[] res new int[ans.size()];for (int i 0; i ans.size(); i ){res[i] ans.get(i);}return res;}// 538.把二叉搜索树转换为累加树// 反中序遍历进行累加int sum;public void traversal(TreeNode root){if (root null) return;traversal(root.right);sum root.val;root.val sum;traversal(root.left);}public TreeNode convertBST(TreeNode root) {sum 0;traversal(root);return root;}}二叉树公共祖先问题
力扣相关题目 236. 二叉树的最近公共祖先 235. 二叉搜索树的最近公共祖先
java代码
class Solution {// 搜索一条边遇到递归函数的返回值如果不为空立刻返回// 236. 二叉树的最近公共祖先public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {if (root null || root p || root q) return root;TreeNode left lowestCommonAncestor(root.left,p,q);TreeNode right lowestCommonAncestor(root.right,p,q);// 如果left 和 right都不为空说明此时root就是最近公共节点// 如果left为空right不为空就返回right说明目标节点是通过right返回的if (left null right null) return null;if (left null right ! null) return right;if (left ! null right null) return left;return root;}// 235. 二叉搜索树的最近公共祖先public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {if (root null) return root;if (root.val p.val root.val q.val){TreeNode left lowestCommonAncestor(root.left,p,q);if (left ! null) return left;}// 如果 cur-val 小于 p-val同时 cur-val 小于 q-val那么就应该向右遍历if (root.val p.val root.val q.val){TreeNode right lowestCommonAncestor(root.right,p,q);if (right ! null) return right;}return root;} }二叉搜索树的修改与构造前序
力扣相关题目 701.二叉搜索树中的插入操作 450.删除二叉搜索树中的节点 669. 修剪二叉搜索树 108.将有序数组转换为二叉搜索树
java代码
class Solution {// 701.二叉搜索树中的插入操作public TreeNode insertIntoBST(TreeNode root, int val) {// 终止条件就是找到遍历的节点为null的时候就是要插入节点的位置了并把插入的节点返回if (root null) return new TreeNode(val);if (root.val val) root.left insertIntoBST(root.left,val);if (root.val val) root.right insertIntoBST(root.right,val);return root;}// 450.删除二叉搜索树中的节点public TreeNode deleteNode(TreeNode root, int key) {if (root null) return root;if (root.val key){// 1.左右孩子都为空叶子节点直接删除节点 返回NULL为根节点// 2.删除节点的左孩子为空右孩子不为空删除节点右孩子补位返回右孩子为根节点// 3.删除节点的右孩子为空左孩子不为空删除节点左孩子补位返回左孩子为根节点// 4.左右孩子节点都不为空则将删除节点的左子树头结点左孩子放到删除节点的右子树的最左面节点的左孩子上返回删除节点右孩子为新的根节点if (root.left null) return root.right;else if (root.right null) return root.left;else{TreeNode curr root.right;while(curr.left ! null){curr curr.left;}curr.left root.left;root root.right;return root;}}if (root.val key) root.left deleteNode(root.left,key);if (root.val key) root.right deleteNode(root.right,key);return root;}// 669. 修剪二叉搜索树public TreeNode trimBST(TreeNode root, int low, int high) {if (root null) return root;// 如果root当前节点的元素小于low的数值那么应该递归右子树并返回右子树符合条件的头结点if (root.val low) return trimBST(root.right,low,high);// 如果root(当前节点)的元素大于high的那么应该递归左子树并返回左子树符合条件的头结点if (root.val high) return trimBST(root.left,low,high);// 接下来要将下一层处理完左子树的结果赋给root-left处理完右子树的结果赋给root-rightroot.left trimBST(root.left,low,high);root.right trimBST(root.right,low,high);return root;}// 108.将有序数组转换为二叉搜索树// 以mid作为分割点然后递归左区间和右区间public TreeNode sortedArrayToBST(int[] nums, int start, int end){if (start end) return null;if (end - start 1) return new TreeNode(nums[start]);int mid start (end - start) / 2;TreeNode root new TreeNode(nums[mid]);root.left sortedArrayToBST(nums,start,mid);root.right sortedArrayToBST(nums,mid 1, end);return root;}public TreeNode sortedArrayToBST(int[] nums) {return sortedArrayToBST(nums,0,nums.length);}}总结
涉及到二叉树的构造无论普通二叉树还是二叉搜索树一定前序都是先构造中节点求普通二叉树的属性一般是后序一般要通过递归函数的返回值做计算求二叉搜索树的属性一定是中序了要不白瞎了有序性了。可以用一个变量存放前一节点状态
