7. 统计路径和等于一个数的路径数量
437. Path Sum III (Easy)
root = [10,5,-3,3,2,null,11,3,-2,null,1], sum = 8 10 / \ 5 -3 / \ \ 3 2 11 / \ \ 3 -2 1 Return 3. The paths that sum to 8 are: 1. 5 -> 3 2. 5 -> 2 -> 1 3. -3 -> 11
路径不一定以 root 开头，也不一定以 leaf 结尾，但是必须连续。
public int pathSum(TreeNode root, int sum) { if (root == null) return 0; int ret = pathSumStartWithRoot(root, sum) + pathSum(root.left, sum) + pathSum(root.right, sum); return ret; } private int pathSumStartWithRoot(TreeNode root, int sum) { if (root == null) return 0; int ret = 0; if (root.val == sum) ret++; ret += pathSumStartWithRoot(root.left, sum - root.val) + pathSumStartWithRoot(root.right, sum - root.val); return ret; }
8. 子树
572. Subtree of Another Tree (Easy)
Given tree s: 3 / \ 4 5 / \ 1 2 Given tree t: 4 / \ 1 2 Return true, because t has the same structure and node values with a subtree of s. Given tree s: 3 / \ 4 5 / \ 1 2 / 0 Given tree t: 4 / \ 1 2 Return false.
public boolean isSubtree(TreeNode s, TreeNode t) { if (s == null) return false; return isSubtreeWithRoot(s, t) || isSubtree(s.left, t) || isSubtree(s.right, t); } private boolean isSubtreeWithRoot(TreeNode s, TreeNode t) { if (t == null && s == null) return true; if (t == null || s == null) return false; if (t.val != s.val) return false; return isSubtreeWithRoot(s.left, t.left) && isSubtreeWithRoot(s.right, t.right); }
9. 树的对称
101. Symmetric Tree (Easy)
public boolean isSymmetric(TreeNode root) { if (root == null) return true; return isSymmetric(root.left, root.right); } private boolean isSymmetric(TreeNode t1, TreeNode t2) { if (t1 == null && t2 == null) return true; if (t1 == null || t2 == null) return false; if (t1.val != t2.val) return false; return isSymmetric(t1.left, t2.right) && isSymmetric(t1.right, t2.left); }
10 求二叉树的镜像
class Solution { public TreeNode invertTree(TreeNode root) { if(root == null) return root; // 先保存最节点，因为 invertTree 已经变化了 TreeNode node = root.left; root.left = invertTree(root.right); root.right = invertTree(node); return root; } }
11. 最小路径
111. Minimum Depth of Binary Tree (Easy)
树的根节点到叶子节点的最小路径长度
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; }
层次遍历
使用 BFS 进行层次遍历。不需要使用两个队列来分别存储当前层的节点和下一层的节点，因为在开始遍历一层的节点时，当前队列中的节点数就是当前层的节点数，只要控制遍历这么多节点数，就能保证这次遍历的都是当前层的节点。
1. 二叉树的层序遍历
给定二叉树，返回其节点值的自下而上级别顺序遍历。
class Solution { public List<List<Integer>> levelOrderBottom(TreeNode root) { List<List<Integer>> res = new LinkedList<>(); Queue<TreeNode> queue = new LinkedList<>(); if(root == null) return res; queue.add(root); while(!queue.isEmpty()){ int count = queue.size(); List<Integer> temp = new LinkedList<>(); for(int i=0; i<count; i++){ TreeNode node = queue.poll(); temp.add(node.val); if(node.left != null) queue.add(node.left); if(node.right != null) queue.add(node.right); } // 每次都添加到第一个位置 res.add(0, temp); } return res; } }
按之字形打印二叉树
请实现一个函数按照之字形打印二叉树，即第一行按照从左到右的顺序打印，第二层按照从右至左的顺序打印，第三行按照从左到右的顺序打印，其他行以此类推。
- 设两个栈，s2存放奇数层，s1存放偶数层
- 遍历s2节点的同时按照左子树、右子树的顺序加入s1，
- 遍历s1节点的同时按照右子树、左子树的顺序加入s2
import java.util.ArrayList; import java.util.Stack; /* public class TreeNode { int val = 0; TreeNode left = null; TreeNode right = null; public TreeNode(int val) { this.val = val; } } */ public class Solution { public ArrayList<ArrayList<Integer> > Print(TreeNode pRoot) { ArrayList<ArrayList<Integer> > res = new ArrayList<ArrayList<Integer> >(); Stack<TreeNode> s1 = new Stack<TreeNode>(); Stack<TreeNode> s2 = new Stack<TreeNode>(); int flag = 1; if(pRoot == null) return res; s2.push(pRoot); ArrayList<Integer> temp = new ArrayList<Integer>(); while(!s1.isEmpty() || !s2.isEmpty()){ if(flag % 2 != 0){ while(!s2.isEmpty()){ TreeNode node = s2.pop(); temp.add(node.val); if(node.left != null){ s1.push(node.left); } if(node.right != null){ s1.push(node.right); } } } if(flag % 2 == 0){ while(!s1.isEmpty()){ TreeNode node = s1.pop(); temp.add(node.val); if(node.right != null){ s2.push(node.right); } if(node.left != null){ s2.push(node.left); } } } res.add(new ArrayList<Integer>(temp)); temp.clear(); flag ++; } return res; } }
前中后序遍历
1 / \ 2 3 / \ \ 4 5 6
- 层次遍历顺序：[1 2 3 4 5 6]
- 前序遍历顺序：[1 2 4 5 3 6]
- 中序遍历顺序：[4 2 5 1 3 6]
- 后序遍历顺序：[4 5 2 6 3 1]
层次遍历使用 BFS 实现，利用的就是 BFS 一层一层遍历的特性；而前序、中序、后序遍历利用了 DFS 实现。
前序、中序、后序遍只是在对节点访问的顺序有一点不同，其它都相同。
① 前序
void dfs(TreeNode root) { visit(root); dfs(root.left); dfs(root.right); }
② 中序
void dfs(TreeNode root) { dfs(root.left); visit(root); dfs(root.right); }
③ 后序
void dfs(TreeNode root) { dfs(root.left); dfs(root.right); visit(root); }
1. 非递归实现二叉树的前序遍历
144. Binary Tree Preorder Traversal (Medium)
public List<Integer> preorderTraversal(TreeNode root) { List<Integer> ret = new ArrayList<>(); Stack<TreeNode> stack = new Stack<>(); stack.push(root); while (!stack.isEmpty()) { TreeNode node = stack.pop(); if (node == null) continue; ret.add(node.val); stack.push(node.right); // 先右后左，保证左子树先遍历 stack.push(node.left); } return ret; }
2. 非递归实现二叉树的后序遍历
145. Binary Tree Postorder Traversal (Medium)
前序遍历为 root -> left -> right，后序遍历为 left -> right -> root。可以修改前序遍历成为 root -> right -> left，那么这个顺序就和后序遍历正好相反。
public List<Integer> postorderTraversal(TreeNode root) { List<Integer> ret = new ArrayList<>(); Stack<TreeNode> stack = new Stack<>(); stack.push(root); while (!stack.isEmpty()) { TreeNode node = stack.pop(); if (node == null) continue; ret.add(node.val); stack.push(node.left); stack.push(node.right); } Collections.reverse(ret); return ret; }
3. 非递归实现二叉树的中序遍历
94. Binary Tree Inorder Traversal (Medium)
public List<Integer> inorderTraversal(TreeNode root) { List<Integer> ret = new ArrayList<>(); if (root == null) return ret; Stack<TreeNode> stack = new Stack<>(); TreeNode cur = root; while (cur != null || !stack.isEmpty()) { while (cur != null) { stack.push(cur); cur = cur.left; } TreeNode node = stack.pop(); ret.add(node.val); cur = node.right; } return ret; }
