经典算法题总结：二叉树篇

二叉树解题的思维模式分两类：

是否可以通过遍历一遍二叉树得到答案？如果可以，用一个 traverse 函数配合外部变量来实现，这叫「遍历」的思维模式。
是否可以定义一个递归函数，通过子问题（子树）的答案推导出原问题的答案？如果可以，写出这个递归函数的定义，并充分利用这个函数的返回值，这叫「分解问题」的思维模式。

无论使用哪种思维模式，你都需要思考：如果单独抽出一个二叉树节点，它需要做什么事情？需要在什么时候（前/中/后序位置）做？其他的节点不用你操心，递归函数会帮你在所有节点上执行相同的操作。

二叉树数据结构定义：

public class TreeNode {int val;TreeNode left;TreeNode right;public TreeNode() {}public TreeNode(int val) {this.val = val;}public TreeNode(int val, TreeNode left, TreeNode right) {this.val = val;this.left = left;this.right = right;}
}

102. 二叉树的层序遍历（⭐️⭐️）

思路

代码

public class LevelOrder {public List<List<Integer>> levelOrder(TreeNode root) {List<List<Integer>> res = new ArrayList<>();Queue<TreeNode> queue = new LinkedList<>();if (root != null) {queue.add(root);}while (!queue.isEmpty()) {int n = queue.size();List<Integer> level = new ArrayList<>();for (int i = 0; i < n; i++) {TreeNode node = queue.poll();level.add(node.val);if (node.left != null) {queue.add(node.left);}if (node.right != null) {queue.add(node.right);}}res.add(level);}return res;}}

复杂度

时间复杂度：O(N)
空间复杂度：O(N)

236. 二叉树的最近公共祖先（⭐️⭐️）

思路

代码

public class LowestCommonAncestor {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);if (left == null && right == null) {return null;} else if (left == null && right != null) {return right;} else if (left != null && right == null) {return left;} else {return root;}}}

复杂度

时间复杂度：O(N)
空间复杂度：O(log(N))

103. 二叉树的锯齿形层序遍历（⭐️⭐）

思路

代码

import java.util.LinkedList;
import java.util.List;
import java.util.Queue;public class ZigzagLevelOrder {public List<List<Integer>> zigzagLevelOrder(TreeNode root) {List<List<Integer>> res = new LinkedList<>();if (root == null) {return res;}Queue<TreeNode> queue = new LinkedList<>();queue.offer(root);boolean flag = true; // 为 true 时从右边开始遍历，false 时从左边开始while (!queue.isEmpty()) {int size = queue.size();LinkedList<Integer> level = new LinkedList<>();for (int i = 0; i < size; i++) {TreeNode node = queue.poll();if (flag) {level.addLast(node.val);} else {level.addFirst(node.val);}if (node.left != null) {queue.offer(node.left);}if (node.right != null) {queue.offer(node.right);}}flag = !flag;res.add(level);}return res;}}

复杂度

时间复杂度：O(N)
空间复杂度：O(N)

124. 二叉树中的最大路径和（⭐️⭐️）

思路

代码

class Solution {int res = Integer.MIN_VALUE;public int maxPathSum(TreeNode root) {traverse(root);return res;}// 返回当前节点能为父亲提供的贡献private int traverse(TreeNode root) {if (root == null) {return 0;}int left = traverse(root.left);int right = traverse(root.right);res = Math.max(res, root.val + left + right);int max = Math.max(root.val + left, root.val + right); // 计算当前节点能为父亲提供的最大贡献return max < 0 ? 0 : max;}}

复杂度

时间复杂度：O(N)
空间复杂度：O(log(N))

94. 二叉树的中序遍历（⭐️⭐️）

思路

中序遍历的过程中收集节点的值。

代码

import java.util.ArrayList;
import java.util.List;public class InorderTraversal {public List<Integer> inorderTraversal(TreeNode root) {List<Integer> list = new ArrayList<>();traverse(root, list);return list;}private void traverse(TreeNode root, List list) {if (root == null) {traverse(root.left, list);list.add(root.val);traverse(root.right, list);}}}

复杂度

时间复杂度：O(N)
空间复杂度：O(N)

199. 二叉树的右视图（⭐️⭐️）

思路

BFS每一层最后一个元素 or DFS 先访问每一层的右边的元素。

代码

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;public class RightSideView {private List<Integer> res = new ArrayList<>();public List<Integer> rightSideViewBFS(TreeNode root) {List<Integer> res = new ArrayList<>();if (root == null) {return res;}Queue<TreeNode> queue = new LinkedList<>();queue.offer(root);while (!queue.isEmpty()) {int size = queue.size();for (int i = 0; i < size; i++) {TreeNode node = queue.poll();if (node.left != null) {queue.offer(node.left);}if (node.right != null) {queue.offer(node.right);}if (i == size - 1) {res.add(node.val);}}}return res;}public List<Integer> rightSideViewDFS(TreeNode root) {DFS(root, 0);return res;}private void DFS(TreeNode root, int depth) {if (root == null) {return;}if (depth == res.size()) {res.add(root.val);}depth++;DFS(root.right, depth);DFS(root.left, depth);}}

复杂度

时间复杂度：O(N)
空间复杂度：方法一：O(N)，方法二：O(log(N))

105. 从前序与中序遍历序列构造二叉树（⭐️⭐️）

思路

代码

import java.util.HashMap;
import java.util.Map;public class BuildTree {private Map<Integer, Integer> map = new HashMap<>();public TreeNode buildTree(int[] preorder, int[] inorder) {for (int i = 0; i < inorder.length; i++) {map.put(inorder[i], i); // 记录中序序列每一个值的位置，用来划分左右子树的节点数量}return traverse(preorder, 0, preorder.length - 1,inorder, 0, inorder.length - 1);}private TreeNode traverse(int[] preorder, int preorderLeft, int preorderRight,int[] inorder, int inorderLeft, int inorderRight) {if (preorderLeft > preorderRight || inorderLeft > inorderRight) {return null;}int rootInInorderLocation = map.get(preorder[preorderLeft]);int sizeLeftSubtree = rootInInorderLocation - inorderLeft;TreeNode root = new TreeNode(preorder[preorderLeft]);root.left = traverse(preorder, preorderLeft + 1, preorderLeft + sizeLeftSubtree,inorder, inorderLeft, rootInInorderLocation - 1);root.right = traverse(preorder, preorderLeft + sizeLeftSubtree + 1, preorderRight,inorder, rootInInorderLocation + 1, inorderRight);return root;}}

复杂度

时间复杂度：O(N)
空间复杂度：O(log(N))

129. 求根节点到叶节点数字之和（⭐️⭐）

思路

DFS

代码

public class SumNumbers {public int sumNumbers(TreeNode root) {return DFS(root, 0);}private int DFS(TreeNode root, int preSum) {if (root == null) {return 0;}int sum = preSum * 10 + root.val;if (root.left == null && root.right == null) {return sum;} else {return DFS(root.left, sum) + DFS(root.right, sum);}}}

复杂度

时间复杂度：
空间复杂度：

104. 二叉树的最大深度（⭐️⭐️）

思路

后序遍历更新当前节点左右子树的最大深度。

代码

class Solution {public int maxDepth(TreeNode root) {if (root == null) {return 0;}int leftHeight = maxDepth(root.left);int rightHeight = maxDepth(root.right);return Math.max(leftHeight, rightHeight) + 1;}}

复杂度