树的高度 104. Maximum Depth of Binary Tree (Easy)
递归计算二叉树左右两边深度,取最大值。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 class Solution { public int maxDepth (TreeNode root) { if (root == null ) return 0 ; int left = maxDepth(root.left); int right = maxDepth(root.right); return Math.max(left, right) + 1 ; } }
平衡树 110. Balanced Binary Tree (Easy)
递归遍历二叉树左右子树深度
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 class Solution { private boolean balance = true ; public boolean isBalanced (TreeNode root) { visitTree(root); return balance; } private int visitTree (TreeNode root) { if (root == null ) return 0 ; int left = visitTree(root.left); int right = visitTree(root.right); if (Math.abs(left - right) > 1 ) this .balance = false ; return Math.max(left, right) + 1 ; } }
两节点的最长路径 543. Diameter of Binary Tree (Easy)
递归遍历二叉树左右子树深度, 路径就是两边子树深度之和
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 class Solution { private int max; public int diameterOfBinaryTree (TreeNode root) { deep(root); return max; } private int deep (TreeNode root) { if (root == null ) return 0 ; int left = deep(root.left); int right = deep(root.right); max = Math.max(max,left+right); return Math.max(left, right) + 1 ; } }
翻转树 226. Invert Binary Tree (Easy)
递归交换左右子树的引用
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 class Solution { public TreeNode invertTree (TreeNode root) { if (root == null ) return root; TreeNode right = root.right; root.right = invertTree(root.left); root.left = invertTree(right); return root; } }
归并两棵树 617. Merge Two Binary Trees (Easy)
递归时如果其中一个节点是空,可以直接复用该节点。如果新建节点,需要拷贝节点的左右子树引用,递归时会用到。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 class Solution { public TreeNode mergeTrees (TreeNode t1, TreeNode t2) { if (t1 == null && t2 == null ) return null ; if (t1 == null ) return t2; if (t2 == null ) return t1; TreeNode root = new TreeNode (t1.val + t2.val); root.left = mergeTrees(t1.left, t2.left); root.right = mergeTrees(t1.right, t2.right); return root; } }
判断路径和是否等于一个数 Leetcode : 112. Path Sum (Easy)
递归查询子树和是否等于目标和
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 class Solution { public boolean hasPathSum (TreeNode root, int sum) { if (root == null ) return false ; if (root.val == sum && root.left == null && root.right == null ) return true ; return hasPathSum(root.left, sum - root.val) || hasPathSum(root.right, sum - root.val); } }
统计路径和等于一个数的路径数量 437. Path Sum III (Easy)
双层递归
以当前节点为起点统计路径和
当前节点以下节点为起点统计路径和
以root为根节点的路径数量= 以root为起点统计路径和+root左节点为起点统计路径和+root右节点为起点统计路径和
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 class Solution { public int pathSum (TreeNode root, int sum) { if (root == null ) return 0 ; return sum(root, sum) + pathSum(root.left, sum) + pathSum(root.right, sum); } private int sum (TreeNode node, int sum) { if (node == null ) return 0 ; int count = 0 ; if (node.val == sum) count++; count += sum(node.left, sum - node.val) + sum(node.right, sum - node.val); return count; } }
子树 572. Subtree of Another Tree (Easy)
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 class Solution { public boolean isSubtree (TreeNode s, TreeNode t) { if (s == null ) return false ; return isSubRoot(s, t) || isSubtree(s.left, t) || isSubtree(s.right, t); } public boolean isSubRoot (TreeNode node, TreeNode t) { if (node == null && t == null ) return true ; if (node == null || t == null ) return false ; if (node.val != t.val) return false ; return isSubRoot(node.left, t.left) && isSubRoot(node.right, t.right); } }
树的对称 101. Symmetric Tree (Easy)
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 class Solution { public boolean isSymmetric (TreeNode root) { if (root == null ) return true ; return isSymmetric(root.left, root.right); } public boolean isSymmetric (TreeNode left, TreeNode right) { if (left == null && right == null ) return true ; if (left == null || right == null ) return false ; if (left.val != right.val) return false ; return isSymmetric(left.left, right.right) && isSymmetric(left.right, right.left); } }
最小路径 111. Minimum Depth of Binary Tree (Easy)
和最大路径类似
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 class Solution { public int minDepth (TreeNode root) { if (root == null ) return 0 ; int left = minDepth(root.left); int right = minDepth(root.right); if (left == 0 || right == 0 ) return left + right + 1 ; return Math.min(left, right) + 1 ; } }
统计左叶子节点的和 404. Sum of Left Leaves (Easy)
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 class Solution { public int sumOfLeftLeaves (TreeNode root) { if (root == null ) return 0 ; if (root.left != null && root.left.left == null && root.left.right == null ) return root.left.val + sumOfLeftLeaves(root.right); return sumOfLeftLeaves(root.left) + sumOfLeftLeaves(root.right); } } ```` #### 相同节点值的最大路径长度 [687. Longest Univalue Path (Easy) ](https: 递归查找左右子树相同节点值最大路径,最大路径的计算:如果相等路径+1 ,如果不相等置为0 。 ```java class Solution { private int path = 0 ; public int longestUnivaluePath (TreeNode root) { visit(root); return path; } private int visit (TreeNode root) { if (root == null ) return 0 ; int left = visit(root.left); int right = visit(root.right); left = (root.left != null && root.val == root.left.val) ? left + 1 : 0 ; right = (root.right != null && root.val == root.right.val)? right + 1 : 0 ; path = Math.max(path, left+right); return Math.max(left, right ); } }
间隔遍历 337. House Robber III (Medium)
递归查询两种情况
如果从当前节点开始
从当前节点的子节点开始
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 class Solution { public int rob (TreeNode root) { if (root == null ) return 0 ; int val1 = root.val, val2 = 0 ; if (root.left != null ) val1+= rob(root.left.left) + rob(root.left.right); if (root.right != null ) val1+= rob(root.right.left) + rob(root.right.right); val2 = rob(root.left) + rob(root.right); return Math.max(val1, val2); } }
找出二叉树中第二小的节点 Second Minimum Node In a Binary Tree (Easy)
第二小节点在子树节点上,如果子树值与根节点相等,继续向下查找
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 class Solution { public int findSecondMinimumValue (TreeNode root) { if (root == null ) return -1 ; if (root.left == null ) return -1 ; int left = root.left.val, right = root.right.val; if (root.val == root.left.val) left = findSecondMinimumValue(root.left); if (root.val == root.right.val) right = findSecondMinimumValue(root.right); if (left != -1 && right != -1 ) return Math.min(left, right); if (left > -1 ) return left; return right; } }
二叉树的层平均值 637. Average of Levels in Binary Tree (Easy)
BFS
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 class Solution { public List<Double> averageOfLevels (TreeNode root) { List<Double> ret = new ArrayList <>(); if (root == null ) return ret; Queue<TreeNode> queue = new LinkedList <>(); queue.add(root); while (!queue.isEmpty()) { int count = queue.size(); double sum = 0d ; for (int i = 0 ; i < count; i++) { TreeNode node = queue.poll(); sum+= node.val; if (node.left != null ) queue.add(node.left); if (node.right != null ) queue.add(node.right); } ret.add(sum/count); } return ret; } }
找树左下角的值 513. Find Bottom Left Tree Value (Easy)
DFS
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 class Solution { private int val = 0 ; public int findBottomLeftValue (TreeNode root) { if (root == null ) return val; Queue<TreeNode> queue = new LinkedList <>(); queue.add(root); while (!queue.isEmpty()) { int count = queue.size(); for (int i = 0 ; i < count; i++) { TreeNode node = queue.poll(); if (i == 0 ) val = node.val; if (node.left != null ) queue.add(node.left); if (node.right != null ) queue.add(node.right); } } return val; } }
非递归实现二叉树的后序遍历 入栈条件: 未访问过该节点 出栈条件: 访问过该节点
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 class Solution { private List<Integer> res = new LinkedList <>(); private Stack<TreeNode> stack = new Stack <>(); private Set<TreeNode> visited = new HashSet <>(); public List<Integer> postorderTraversal (TreeNode root) { if (root == null ) return res; stack.push(root); while (!stack.isEmpty()) { TreeNode node = stack.peek(); if ((node.left == null && node.right == null ) || visited.contains(node)) { TreeNode i = stack.pop(); res.add(i.val); } else { visited.add(node); if (node.right != null ) stack.push(node.right); if (node.left != null ) stack.push(node.left); } } return res; } private void visit (TreeNode root) { if (root == null ) return ; visit(root.left); visit(root.right); res.add(root.val); } }
非递归实现二叉树的前序遍历 入栈条件: 无 出栈条件: 直接出栈
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 class Solution { private List<Integer> res = new LinkedList <>(); private Stack<TreeNode> stack = new Stack <>(); public List<Integer> preorderTraversal (TreeNode root) { if (root == null ) return res; stack.push(root); while (!stack.isEmpty()) { TreeNode node = stack.pop(); res.add(node.val); if (node.right != null ) stack.push(node.right); if (node.left != null ) stack.push(node.left); } return res; } }
非递归实现二叉树的中序遍历 入栈条件: 未访问过该节点 出栈条件: 访问过该节点 入栈顺序: right -> middle -> left
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 class Solution { private List<Integer> res = new LinkedList <>(); private Stack<TreeNode> stack = new Stack <>(); private Set<TreeNode> visited = new HashSet <>(); public List<Integer> inorderTraversal (TreeNode root) { if (root == null ) return res; push(root); while (!stack.isEmpty()) { TreeNode node = stack.pop(); if ((node.left == null && node.right == null ) || visited.contains(node)) { res.add(node.val); } else { push(node); } } return res; } private void push (TreeNode root) { if (root == null ) return ; visited.add(root); if (root.right != null ) stack.push(root.right); stack.push(root); if (root.left != null ) stack.push(root.left); } }