本文解决的问题: 按主题归纳 二叉树 相关高频题型与通用解法。
适用范围: LeetCode 中文站题目,示例主要使用 Java。
阅读建议: 先识别数据结构与不变量,再结合题目约束选择算法,不要只记忆代码。
二叉树 给定一个二叉树的根节点 root ,返回 它的 中序 遍历 。
进阶: 递归算法很简单,你可以通过迭代算法完成吗?
提示: 树中节点数目在范围 [0, 100] 内
100 <= Node.val <= 100
示例: 
1 2 输入:root = [1,null,2,3] 输出:[1,3,2]
代码:
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 List<Integer> inorderTraversal (TreeNode root) { List<Integer> res = new ArrayList <>(); if (root == null ) { return res; } TreeNode current = root; while (current != null ) { if (current.left == null ) { res.add(current.val); current = current.right; } else { TreeNode predecessor = current.left; while (predecessor.right != null && predecessor.right != current) { predecessor = predecessor.right; } if (predecessor.right == null ) { predecessor.right = current; current = current.left; } else { predecessor.right = null ; res.add(current.val); current = current.right; } } } return res; } }
给定一个二叉树 root ,返回其最大深度。
二叉树的 最大深度 是指从根节点到最远叶子节点的最长路径上的节点数。
提示: 树中节点的数量在 [0, 104] 区间内。
100 <= Node.val <= 100
示例: 
1 2 输入:root = [3,9,20,null,null,15,7] 输出:3
代码:
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 55 class Solution { public int maxDepth (TreeNode root) { if (root == null ) { return 0 ; } else { int leftHeight = maxDepth(root.left); int rightHeight = maxDepth(root.right); return Math.max(leftHeight, rightHeight) + 1 ; } } } class Solution { public int maxDepth (TreeNode root) { if (root == null ) { return 0 ; } Queue<TreeNode> queue = new LinkedList <TreeNode>(); queue.offer(root); int ans = 0 ; while (!queue.isEmpty()) { int size = queue.size(); while (size > 0 ) { TreeNode node = queue.poll(); if (node.left != null ) { queue.offer(node.left); } if (node.right != null ) { queue.offer(node.right); } size--; } ans++; } return ans; } }
给定一个二叉搜索树的根节点 root ,和一个整数 k ,请你设计一个算法查找其中第 k 小的元素(从 1 开始计数)。
提示:
树中的节点数为 n 。
1 <= k <= n <= 104
0 <= Node.val <= 104
示例:
1 2 输入:root = [3,1,4,null,2], k = 1 输出:1
1 2 输入:root = [5,3,6,2,4,null,null,1], k = 3 输出:3
代码:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 public int kthSmallest (TreeNode root, int k) { Deque<TreeNode> stack = new ArrayDeque <TreeNode>(); while (root != null || !stack.isEmpty()) { while (root != null ) { stack.push(root); root = root.left; } root = stack.pop(); --k; if (k == 0 ) { break ; } root = root.right; } return root.val; }
给你一棵二叉树的根节点 root ,翻转这棵二叉树,并返回其根节点。
提示:
树中节点数目范围在 [0, 100] 内
-100 <= Node.val <= 100
示例 1:
1 2 输入:root = [4,2,7,1,3,6,9] 输出:[4,7,2,9,6,3,1]
示例 2:
1 2 输入:root = [2,1,3] 输出:[2,3,1]
示例 3:
代码:
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 class Solution { public TreeNode invertTree (TreeNode root) { if (root == null ) { return null ; } TreeNode left = invertTree(root.left); TreeNode right = invertTree(root.right); root.left = right; root.right = left; return root; } }
给你二叉树的根节点 root ,返回其节点值的 层序遍历 。 (即逐层地,从左到右访问所有节点)。
提示:
树中节点数目在范围 [0, 2000] 内
-1000 <= Node.val <= 1000
示例:
1 2 3 4 5 6 7 8 9 10 输入:root = [3,9,20,null,null,15,7] 输出:[[3],[9,20],[15,7]] 示例 2: 输入:root = [1] 输出:[[1]] 示例 3: 输入: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 25 26 public List<List<Integer>> levelOrder (TreeNode root) { List<List<Integer>> ret = new ArrayList <List<Integer>>(); if (root == null ) { return ret; } Queue<TreeNode> queue = new LinkedList <TreeNode>(); queue.offer(root); while (!queue.isEmpty()) { List<Integer> level = new ArrayList <Integer>(); int currentLevelSize = queue.size(); for (int i = 1 ; i <= currentLevelSize; ++i) { TreeNode node = queue.poll(); level.add(node.val); if (node.left != null ) { queue.offer(node.left); } if (node.right != null ) { queue.offer(node.right); } } ret.add(level); } return ret; }
给你一个二叉树的根节点 root ,判断其是否是一个有效的二叉搜索树。
有效 二叉搜索树定义如下:
节点的左子树只包含 小于 当前节点的数。
节点的右子树只包含 大于 当前节点的数。
所有左子树和右子树自身必须也是二叉搜索树。
提示:
树中节点数目范围在 [1, 104] 内
-231 <= Node.val <= 231 - 1
示例 1:
1 2 输入:root = [2,1,3] 输出:true
示例 2:
1 2 3 输入:root = [5,1,4,null,null,3,6] 输出:false 解释:根节点的值是 5 ,但是右子节点的值是 4 。
代码:
1 2 3 4 5 6 7 8 9 10 11 12 13 public boolean isValidBST (TreeNode root) { return isValidBST(root, Long.MIN_VALUE, Long.MAX_VALUE); } private boolean isValidBST (TreeNode root, long min, long max) { if (root == null ) { return true ; } if (root.val <= min || root.val >= max) { return false ; } return isValidBST(root.left, min, root.val) && isValidBST(root.right, root.val, max); }
有效 二叉搜索树定义如下:
节点的左子树只包含** 小于 **当前节点的数。
节点的右子树只包含 大于 当前节点的数。
所有左子树和右子树自身必须也是二叉搜索树。
提示:
树中节点数目在范围 [1, 1000] 内
-100 <= Node.val <= 100
进阶: 你可以运用递归和迭代两种方法解决这个问题吗?
示例 1:
1 2 输入:root = [1,2,2,3,4,4,3] 输出:true
示例 2:
1 2 输入:root = [1,2,2,null,3,null,3] 输出:false
代码:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 class Solution { public boolean isSymmetric (TreeNode root) { return root == null || rece(root.left, root.right); } private boolean rece (TreeNode L, TreeNode R) { if (L == null && R == null ) return true ; if (L == null || R== null || L.val != R.val) return false ; return rece(L.right, R.left) && rece(L.left, R.right); } }
给你一棵二叉树的根节点,返回该树的 直径 。
二叉树的 直径 是指树中任意两个节点之间最长路径的 长度 。这条路径可能经过也可能不经过根节点 root 。
两节点之间路径的 长度 由它们之间边数表示。
提示:
树中节点数目在范围 [1, 10^4] 内
-100 <= Node.val <= 100
示例 1:
1 2 3 输入:root = [1,2,3,4,5] 输出:3 解释:3 ,取路径 [4,2,1,3] 或 [5,2,1,3] 的长度。
示例 2:
代码:
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 class Solution { int ans = 0 ; public int diameterOfBinaryTree (TreeNode root) { ans = 1 ; dfs(root); return ans - 1 ; } private int dfs (TreeNode root) { if (root == null ) { return 0 ; } int l = dfs(root.left); int r = dfs(root.right); ans = Math.max(ans, l+r+1 ); return Math.max(l, r) + 1 ; } }
给你一个整数数组 nums ,其中元素已经按 升序 排列,请你将其转换为一棵 平衡 二叉搜索树。
提示:
1 <= nums.length <= 10^4
-10^4 <= nums[i] <= 10^4
nums 按 严格递增 顺序排列
示例 1:
1 2 3 4 输入:nums = [-10,-3,0,5,9] 输出:[0,-3,9,-10,null,5] 解释:[0,-10,5,null,-3,null,9] 也将被视为正确答案: 
示例 2:
1 2 3 输入:nums = [1,3] 输出:[3,1] 解释:[1,null,3] 和 [3,1] 都是高度平衡二叉搜索树。
代码:
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 { Random rand = new Random (); public TreeNode sortedArrayToBST (int [] nums) { return helper(nums, 0 , nums.length - 1 ); } public TreeNode helper (int [] nums, int left, int right) { if (left > right) { return null ; } int mid = (left + right + rand.nextInt(2 )) / 2 ; TreeNode root = new TreeNode (nums[mid]); root.left = helper(nums, left, mid - 1 ); root.right = helper(nums, mid + 1 , right); return root; } }
给定一个二叉树的 根节点 root,想象自己站在它的右侧,按照从顶部到底部的顺序,返回从右侧所能看到的节点值。
提示:
二叉树的节点个数的范围是 [0,100]
-100 <= Node.val <= 100
示例 1:
输入: root = [1,2,3,null,5,null,4]
输出: [1,3,4]
解释:
示例 2:
输入: root = [1,2,3,4,null,null,null,5]
输出: [1,3,4,5]
解释:
示例 3:
输入: root = [1,null,3]
输出: [1,3]
示例 4:
输入: 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 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 class Solution { public List<Integer> rightSideView (TreeNode root) { Map<Integer, Integer> rightmostValueAtDepth = new HashMap <Integer, Integer>(); int max_depth = -1 ; Deque<TreeNode> nodeStack = new LinkedList <TreeNode>(); Deque<Integer> depthStack = new LinkedList <Integer>(); nodeStack.push(root); depthStack.push(0 ); while (!nodeStack.isEmpty()) { TreeNode node = nodeStack.pop(); int depth = depthStack.pop(); if (node != null ) { max_depth = Math.max(max_depth, depth); if (!rightmostValueAtDepth.containsKey(depth)) { rightmostValueAtDepth.put(depth, node.val); } nodeStack.push(node.left); nodeStack.push(node.right); depthStack.push(depth + 1 ); depthStack.push(depth + 1 ); } } List<Integer> rightView = new ArrayList <Integer>(); for (int depth = 0 ; depth <= max_depth; depth++) { rightView.add(rightmostValueAtDepth.get(depth)); } return rightView; } }
给你二叉树的根结点 root ,请你将它展开为一个单链表:
展开后的单链表应该同样使用 TreeNode ,其中 right 子指针指向链表中下一个结点,而左子指针始终为 null 。
展开后的单链表应该与二叉树的先序遍历 顺序相同。
提示:
树中结点数在范围 [0, 2000] 内
-100 <= Node.val <= 100
进阶: 你可以使用原地算法(O(1) 额外空间)展开这棵树吗?
示例 1:
1 2 输入:root = [1,2,5,3,4,null,6] 输出:[1,null,2,null,3,null,4,null,5,null,6]
示例 2:
示例 3:
代码:
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 class Solution { public void flatten (TreeNode root) { List<TreeNode> list = new ArrayList <TreeNode>(); preorderTraversal(root, list); int size = list.size(); for (int i = 1 ; i < size; i++) { TreeNode prev = list.get(i - 1 ), curr = list.get(i); prev.left = null ; prev.right = curr; } } public void preorderTraversal (TreeNode root, List<TreeNode> list) { if (root != null ) { list.add(root); preorderTraversal(root.left, list); preorderTraversal(root.right, list); } } } class Solution { public void flatten (TreeNode root) { List<TreeNode> list = new ArrayList <TreeNode>(); Deque<TreeNode> stack = new LinkedList <TreeNode>(); TreeNode node = root; while (node != null || !stack.isEmpty()) { while (node != null ) { list.add(node); stack.push(node); node = node.left; } node = stack.pop(); node = node.right; } int size = list.size(); for (int i = 1 ; i < size; i++) { TreeNode prev = list.get(i - 1 ), curr = list.get(i); prev.left = null ; prev.right = curr; } } }
给定两个整数数组 preorder 和 inorder ,其中 preorder 是二叉树的 先序遍历 , inorder 是同一棵树的 中序遍历 ,请构造二叉树并返回其根节点。
提示:
1 <= preorder.length <= 3000
inorder.length == preorder.length
-3000 <= preorder[i], inorder[i] <= 3000
preorder 和 inorder 均 无重复 元素
inorder 均出现在 preorder
preorder 保证 为二叉树的前序遍历序列
inorder 保证 为二叉树的中序遍历序列
示例 1:
1 2 输入: preorder = [3,9,20,15,7], inorder = [9,3,15,20,7] 输出: [3,9,20,null,null,15,7]
示例 2:
1 2 输入: preorder = [-1], inorder = [-1] 输出: [-1]
代码:
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 Map<Integer, Integer> indexMap; public TreeNode myBuildTree (int [] preorder, int [] inorder, int preorder_left, int preorder_right, int inorder_left, int inorder_right) { if (preorder_left > preorder_right) { return null ; } int preorder_root = preorder_left; int inorder_root = indexMap.get(preorder[preorder_root]); TreeNode root = new TreeNode (preorder[preorder_root]); int size_left_subtree = inorder_root - inorder_left; root.left = myBuildTree(preorder, inorder, preorder_left + 1 , preorder_left + size_left_subtree, inorder_left, inorder_root - 1 ); root.right = myBuildTree(preorder, inorder, preorder_left + size_left_subtree + 1 , preorder_right, inorder_root + 1 , inorder_right); return root; } public TreeNode buildTree (int [] preorder, int [] inorder) { int n = preorder.length; indexMap = new HashMap <Integer, Integer>(); for (int i = 0 ; i < n; i++) { indexMap.put(inorder[i], i); } return myBuildTree(preorder, inorder, 0 , n - 1 , 0 , n - 1 ); } }
给定一个二叉树的根节点 root ,和一个整数 targetSum ,求该二叉树里节点值之和等于 targetSum 的 路径 的数目。
路径 不需要从根节点开始,也不需要在叶子节点结束,但是路径方向必须是向下的(只能从父节点到子节点)。
提示:
二叉树的节点个数的范围是 [0,1000]
-10^9 <= Node.val <= 10^9
-1000 <= targetSum <= 1000
示例 1:
1 2 3 输入:root = [10,5,-3,3,2,null,11,3,-2,null,1], targetSum = 8 输出:3 解释:和等于 8 的路径有 3 条,如图所示。
示例 2:
1 2 输入:root = [5,4,8,11,null,13,4,7,2,null,null,5,1], targetSum = 22 输出:3
代码:
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 55 56 class Solution { public int pathSum (TreeNode root, long targetSum) { if (root == null ) { return 0 ; } int ret = rootSum(root, targetSum); ret += pathSum(root.left, targetSum); ret += pathSum(root.right, targetSum); return ret; } public int rootSum (TreeNode root, long targetSum) { int ret = 0 ; if (root == null ) { return 0 ; } int val = root.val; if (val == targetSum) { ret++; } ret += rootSum(root.left, targetSum - val); ret += rootSum(root.right, targetSum - val); return ret; } } class Solution { public int pathSum (TreeNode root, int targetSum) { Map<Long, Integer> prefix = new HashMap <Long, Integer>(); prefix.put(0L , 1 ); return dfs(root, prefix, 0 , targetSum); } public int dfs (TreeNode root, Map<Long, Integer> prefix, long curr, int targetSum) { if (root == null ) { return 0 ; } int ret = 0 ; curr += root.val; ret = prefix.getOrDefault(curr - targetSum, 0 ); prefix.put(curr, prefix.getOrDefault(curr, 0 ) + 1 ); ret += dfs(root.left, prefix, curr, targetSum); ret += dfs(root.right, prefix, curr, targetSum); prefix.put(curr, prefix.getOrDefault(curr, 0 ) - 1 ); return ret; } }
给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。
在有根树中,节点 p、q 的最近公共祖先,是同时作为两者祖先且深度最大的节点;一个节点也可以是它自己的祖先。
提示:
树中节点数目在范围 [2, 10^5] 内。
-10^9 <= Node.val <= 10^9
所有 Node.val 互不相同 。
p != q
p 和 q 均存在于给定的二叉树中。
示例 1:
1 2 3 输入:root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1 输出:3 解释:节点 5 和节点 1 的最近公共祖先是节点 3 。
示例 2:
1 2 3 输入:root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4 输出:5 解释:节点 5 和节点 4 的最近公共祖先是节点 5 。因为根据定义最近公共祖先节点可以为节点本身。
示例 3:
1 2 输入:root = [1,2], p = 1, q = 2 输出:1
代码:
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 { private TreeNode ans; public Solution () { this .ans = null ; } private boolean dfs (TreeNode root, TreeNode p, TreeNode q) { if (root == null ) return false ; boolean lson = dfs(root.left, p, q); boolean rson = dfs(root.right, p, q); if ((lson && rson) || ((root.val == p.val || root.val == q.val) && (lson || rson))) { ans = root; } return lson || rson || (root.val == p.val || root.val == q.val); } public TreeNode lowestCommonAncestor (TreeNode root, TreeNode p, TreeNode q) { this .dfs(root, p, q); return this .ans; } }
二叉树中的** 路径** 被定义为一条节点序列,序列中每对相邻节点之间都存在一条边。同一个节点在一条路径序列中 至多出现一次 。该路径** 至少包含一个 **节点,且不一定经过根节点。
路径和 是路径中各节点值的总和。
给你一个二叉树的根节点 root ,返回其 最大路径和 。
提示:
树中节点数目范围是 [1, 3 * 10^4]
-1000 <= Node.val <= 1000
示例 1:
1 2 3 输入:root = [1,2,3] 输出:6 解释:最优路径是 2 -> 1 -> 3 ,路径和为 2 + 1 + 3 = 6
示例 2:
1 2 3 输入:root = [-10,9,20,null,null,15,7] 输出:42 解释:最优路径是 15 -> 20 -> 7 ,路径和为 15 + 20 + 7 = 42
代码:
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 class Solution { int maxSum = Integer.MIN_VALUE; public int maxPathSum (TreeNode root) { maxGain(root); return maxSum; } public int maxGain (TreeNode node) { if (node == null ) { return 0 ; } int leftGain = Math.max(maxGain(node.left), 0 ); int rightGain = Math.max(maxGain(node.right), 0 ); int priceNewpath = node.val + leftGain + rightGain; maxSum = Math.max(maxSum, priceNewpath); return node.val + Math.max(leftGain, rightGain); } }
参考资料