常见的二叉树系统题解（一）：https://developer.aliyun.com/article/1416666
修剪二叉搜索树
- 修剪二叉搜索树
给定一个二叉搜索树，同时给定最小边界L 和最大边界 R。通过修剪二叉搜索树，使得所有节点的值在[L, R]中 (R>=L) 。你可能需要改变树的根节点，所以结果应当返回修剪好的二叉搜索树的新的根节点。
示例 1:
输入: 1 / \ 0 2 L = 1 R = 2 输出: 1 \ 2
示例 2:
输入: 3 / \ 0 4 \ 2 / 1 L = 1 R = 3 输出: 3 / 2 / 1
public TreeNode trimBST(TreeNode root, int L, int R) { if (root == null) { return null; } if (root.val > R) { return trimBST(root.left, L, R); } if (root.val < L) { return trimBST(root.right, L, R); } root.left = trimBST(root.left, L, R); root.right = trimBST(root.right, L, R); return root; }
将有序数组转换为二叉搜索树
- 将有序数组转换为二叉搜索树
将一个按照升序排列的有序数组，转换为一棵高度平衡二叉搜索树。
本题中，一个高度平衡二叉树是指一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1。
示例:
给定有序数组: [-10,-3,0,5,9], 一个可能的答案是：[0,-3,9,-10,null,5]，它可以表示下面这个高度平衡二叉搜索树： 0 / \ -3 9 / / -10 5
public TreeNode sortedArrayToBST(int[] nums) { if (nums == null || nums.length == 0) { return null; } return robot(nums, 0, nums.length - 1); } private TreeNode robot(int[] nums, int start, int end) { if (start > end) { return null; } int mid = start + (end - start) / 2; TreeNode root = new TreeNode(nums[mid]); root.left = robot(nums, start, mid - 1); root.right = robot(nums, mid + 1, end); return root; }
二叉搜索树迭代器
- 二叉搜索树迭代器
实现一个二叉搜索树迭代器。你将使用二叉搜索树的根节点初始化迭代器。
调用 next() 将返回二叉搜索树中的下一个最小的数。
示例：
BSTIterator iterator = new BSTIterator(root); iterator.next(); // 返回 3 iterator.next(); // 返回 7 iterator.hasNext(); // 返回 true iterator.next(); // 返回 9 iterator.hasNext(); // 返回 true iterator.next(); // 返回 15 iterator.hasNext(); // 返回 true iterator.next(); // 返回 20 iterator.hasNext(); // 返回 false
提示：
- next() 和 hasNext() 操作的时间复杂度是 O(1)，并使用 O(h) 内存，其中 h 是树的高度。
- 你可以假设 next() 调用总是有效的，也就是说，当调用 next() 时，BST 中至少存在一个下一个最小的数。
class BSTIterator { Stack<TreeNode> vector = new Stack<>(); TreeNode current; public BSTIterator(TreeNode root) { current = root; // 一直放入左儿子（左） while (current != null) { vector.push(current); current = current.left; } } /** @return whether we have a next smallest number */ public boolean hasNext() { return !vector.isEmpty() || current != null; } /** @return the next smallest number */ public int next() { // 一直放入左儿子（左） while (current != null) { vector.push(current); current = current.left; } int ans = 0; // 访问当前元素（中），把右儿子入栈（右） if (!vector.isEmpty()) { current = vector.pop(); ans = current.val; current = current.right; } return ans; } } /** * Your BSTIterator object will be instantiated and called as such: * BSTIterator obj = new BSTIterator(root); * int param_1 = obj.next(); * boolean param_2 = obj.hasNext(); */
二叉搜索树中第K小的元素
- 二叉搜索树中第K小的元素
给定一个二叉搜索树，编写一个函数 kthSmallest 来查找其中第 k 个最小的元素。
说明：
你可以假设 k 总是有效的，1 ≤ k ≤ 二叉搜索树元素个数。
示例 1:
输入: root = [3,1,4,null,2], k = 1 3 / \ 1 4 \ 2 输出: 1
示例 2:
输入: root = [5,3,6,2,4,null,null,1], k = 3 5 / \ 3 6 / \ 2 4 / 1 输出: 3
进阶：
如果二叉搜索树经常被修改（插入/删除操作）并且你需要频繁地查找第 k 小的值，你将如何优化 kthSmallest 函数？
int ans = 0; int count = 0; public int kthSmallest(TreeNode root, int k) { count = k; robot(root); return ans; } private void robot(TreeNode root) { if (root == null) { return; } robot(root.left); if (--count == 0) { ans = root.val; return; } robot(root.right); }
二叉搜索树的最近公共祖先
- 二叉搜索树的最近公共祖先
给定一个二叉搜索树, 找到该树中两个指定节点的最近公共祖先。
百度百科中最近公共祖先的定义为：“对于有根树 T 的两个结点 p、q，最近公共祖先表示为一个结点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”
例如，给定如下二叉搜索树: root = [6,2,8,0,4,7,9,null,null,3,5]
示例 1:
输入: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 8 输出: 6 解释: 节点 2 和节点 8 的最近公共祖先是 6。
示例 2:
输入: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 4 输出: 2 解释: 节点 2 和节点 4 的最近公共祖先是 2, 因为根据定义最近公共祖先节点可以为节点本身。
说明:
- 所有节点的值都是唯一的。
- p、q 为不同节点且均存在于给定的二叉搜索树中。
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) { if (root == null || p == null || q == null) { return null; } TreeNode left = lowestCommonAncestor(root.left, p, q); if (root.val <= Math.max(p.val, q.val) && root.val >= Math.min(p.val, q.val)) { return root; } TreeNode right = lowestCommonAncestor(root.right, p, q); return left == null ? right : left; }
删除二叉搜索树中的节点
- 删除二叉搜索树中的节点
给定一个二叉搜索树的根节点 root 和一个值 key，删除二叉搜索树中的 key 对应的节点，并保证二叉搜索树的性质不变。返回二叉搜索树（有可能被更新）的根节点的引用。
一般来说，删除节点可分为两个步骤：
- 首先找到需要删除的节点；
- 如果找到了，删除它。
说明： 要求算法时间复杂度为 O(h)，h 为树的高度。
示例:
root = [5,3,6,2,4,null,7] key = 3 5 / \ 3 6 / \ \ 2 4 7 给定需要删除的节点值是 3，所以我们首先找到 3 这个节点，然后删除它。 一个正确的答案是 [5,4,6,2,null,null,7], 如下图所示。 5 / \ 4 6 / \ 2 7 另一个正确答案是 [5,2,6,null,4,null,7]。 5 / \ 2 6 \ \ 4 7
// todo 题目复杂，面试时不会常考，考虑忽略此题目
二叉搜索树中的搜索
- 二叉搜索树中的搜索
给定二叉搜索树（BST）的根节点和一个值。 你需要在BST中找到节点值等于给定值的节点。 返回以该节点为根的子树。 如果节点不存在，则返回 NULL。
例如，
给定二叉搜索树: 4 / \ 2 7 / \ 1 3 和值: 2
你应该返回如下子树:
2 / \ 1 3
在上述示例中，如果要找的值是 5，但因为没有节点值为 5，我们应该返回 NULL。
public TreeNode searchBST(TreeNode root, int val) { if (root == null || root.val == val) { return root; } if (root.val < val) { return searchBST(root.right, val); } if (root.val > val) { return searchBST(root.left, val); } return null; }
二叉搜索树中的插入操作
给定二叉搜索树（BST）的根节点和要插入树中的值，将值插入二叉搜索树。 返回插入后二叉搜索树的根节点。 保证原始二叉搜索树中不存在新值。
注意，可能存在多种有效的插入方式，只要树在插入后仍保持为二叉搜索树即可。 你可以返回任意有效的结果。
例如,
给定二叉搜索树: 4 / \ 2 7 / \ 1 3 和 插入的值: 5
你可以返回这个二叉搜索树:
4 / \ 2 7 / \ / 1 3 5
或者这个树也是有效的:
5 / \ 2 7 / \ 1 3 \ 4
public TreeNode insertIntoBST(TreeNode root, int val) { if (root == null) { return new TreeNode(val); } if (root.val > val) { root.left = insertIntoBST(root.left, val); } else { root.right = insertIntoBST(root.right, val); } return root; }
深搜、广搜
相同的树
给定两个二叉树，编写一个函数来检验它们是否相同。
如果两个树在结构上相同，并且节点具有相同的值，则认为它们是相同的。
示例 1:
输入: 1 1 / \ / \ 2 3 2 3 [1,2,3], [1,2,3] 输出: true
示例 2:
输入: 1 1 / \ 2 2 [1,2], [1,null,2] 输出: false
示例 3:
输入: 1 1 / \ / \ 2 1 1 2 [1,2,1], [1,1,2] 输出: false
public boolean isSameTree(TreeNode p, TreeNode q) { if (p == q) { return true; } if (p == null || q == null) { return false; } return p.val == q.val && isSameTree(p.left, q.left) && isSameTree(p.right, q.right); }
对称二叉树
给定一个二叉树，检查它是否是镜像对称的。
例如，二叉树 [1,2,2,3,4,4,3] 是对称的。
1 / \ 2 2 / \ / \ 3 4 4 3
但是下面这个 [1,2,2,null,3,null,3] 则不是镜像对称的:
1 / \ 2 2 \ \ 3 3
说明:
如果你可以运用递归和迭代两种方法解决这个问题，会很加分。
递归
public boolean isSymmetric(TreeNode root) { return robot(root, root); } boolean robot(TreeNode p, TreeNode q) { if (p == null && q == null) { return true; } if (p == null || q == null) { return false; } return p.val == q.val && robot(p.left, q.right) && robot(p.right, q.left); }
迭代
public boolean isSymmetric2(TreeNode root) { if (root == null) { return true; } Stack<TreeNode> stack = new Stack<>(); stack.push(root.left); stack.push(root.right); while (!stack.isEmpty()) { TreeNode p = stack.pop(); TreeNode q = stack.pop(); if (p == null && q == null) { continue; } if (p == null || q == null) { return false; } if (p.val != q.val) { return false; } stack.push(p.left); stack.push(q.right); stack.push(p.right); stack.push(q.left); } return true; }
翻转二叉树
- 翻转二叉树
示例：
输入：
4 / \ 2 7 / \ / \ 1 3 6 9
输出：
4 / \ 7 2 / \ / \ 9 6 3 1
备注:
这个问题是受到 Max Howell 的 原问题 启发的 ：
谷歌：我们90％的工程师使用您编写的软件(Homebrew)，但是您却无法在面试时在白板上写出翻转二叉树这道题，这太糟糕了。
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; }
二叉树的最大深度
- 二叉树的最大深度
给定一个二叉树，找出其最大深度。
二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。
说明: 叶子节点是指没有子节点的节点。
示例：
给定二叉树 [3,9,20,null,null,15,7]，
3 / \ 9 20 / \ 15 7
返回它的最大深度 3 。
public int maxDepth(TreeNode root) { if (root == null) { return 0; } int left = maxDepth(root.left); int right = maxDepth(root.right); return left > right ? (left + 1) : (right + 1); }
二叉树的最小深度
- 二叉树的最小深度
给定一个二叉树，找出其最小深度。
最小深度是从根节点到最近叶子节点的最短路径上的节点数量。
说明: 叶子节点是指没有子节点的节点。
示例:
给定二叉树 [3,9,20,null,null,15,7],
3 / \ 9 20 / \ 15 7
返回它的最小深度 2.
public int minDepth(TreeNode root) { if (root == null) { return 0; } int left = minDepth(root.left); int right = minDepth(root.right); return (left == 0 || right == 0) ? (left + right + 1) : Math.min(left, right) + 1; }
平衡二叉树
- 平衡二叉树
给定一个二叉树，判断它是否是高度平衡的二叉树。
本题中，一棵高度平衡二叉树定义为：
一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过1。
示例 1:
给定二叉树 [3,9,20,null,null,15,7]
3 / \ 9 20 / \ 15 7
返回 true 。
示例 2:
给定二叉树 [1,2,2,3,3,null,null,4,4]
1 / \ 2 2 / \ 3 3 / \ 4 4
返回 false 。
public boolean isBalanced(TreeNode root) { if (root == null) { return true; } return Math.abs(depth(root.left) - depth(root.right)) <= 1 && isBalanced(root.left) && isBalanced(root.right); } int depth(TreeNode node) { if (node == null) { return 0; } return Math.max(depth(node.left), depth(node.right)) + 1; }
完全二叉树的节点个数
给出一个完全二叉树，求出该树的节点个数。
说明：
完全二叉树的定义如下：在完全二叉树中，除了最底层节点可能没填满外，其余每层节点数都达到最大值，并且最下面一层的节点都集中在该层最左边的若干位置。若最底层为第 h 层，则该层包含 1~ 2^h 个节点。
示例:
输入:
1 / \ 2 3 / \ / 4 5 6 输出: 6
public int countNodes(TreeNode root) { if (root == null) { return 0; } int left = 0; int right = 0; TreeNode p = root; while (p != null) { p = p.left; left++; } p = root; while (p != null) { p = p.right; right++; } if (left == right) { return (1 << left) - 1; } return countNodes(root.left) + countNodes(root.right) + 1; }
二叉树最大宽度
- 二叉树最大宽度
给定一个二叉树，编写一个函数来获取这个树的最大宽度。树的宽度是所有层中的最大宽度。这个二叉树与 满二叉树（full binary tree） 结构相同，但一些节点为空。
每一层的宽度被定义为两个端点（该层最左和最右的非空节点，两端点间的null节点也计入长度）之间的长度。
示例 1:
输入: 1 / \ 3 2 / \ \ 5 3 9 输出: 4 解释: 最大值出现在树的第 3 层，宽度为 4 (5,3,null,9)。
示例 2:
输入: 1 / 3 / \ 5 3 输出: 2 解释: 最大值出现在树的第 3 层，宽度为 2 (5,3)。
示例 3:
输入: 1 / \ 3 2 / 5 输出: 2 解释: 最大值出现在树的第 2 层，宽度为 2 (3,2)。
示例 4:
输入: 1 / \ 3 2 / \ 5 9 / \ 6 7 输出: 8 解释: 最大值出现在树的第 4 层，宽度为 8 (6,null,null,null,null,null,null,7)。
注意: 答案在32位有符号整数的表示范围内。
public int widthOfBinaryTree(TreeNode root) { int[] ans = new int[1]; robot(root, ans, new ArrayList<>(), 0, 1); return ans[0]; } private void robot(TreeNode root, int[] ans, ArrayList<Integer> leftIndexes, int level, int index) { if (root == null) { return; } if (leftIndexes.size() <= level) { leftIndexes.add(index); } ans[0] = Math.max(ans[0], index - leftIndexes.get(level) + 1); robot(root.left, ans, leftIndexes, level + 1, 2 * index); robot(root.right, ans, leftIndexes, level + 1, 2 * index + 1); }
二叉树的直径
- 二叉树的直径
给定一棵二叉树，你需要计算它的直径长度。一棵二叉树的直径长度是任意两个结点路径长度中的最大值。这条路径可能穿过根结点。
示例 :
给定二叉树
1 / \ 2 3 / \ 4 5
返回 3, 它的长度是路径 [4,2,1,3] 或者 [5,2,1,3]。
注意：两结点之间的路径长度是以它们之间边的数目表示。
public int diameterOfBinaryTree(TreeNode root) { int[] ans = new int[1]; robot(root, ans); return ans[0]; } private int robot(TreeNode root, int[] ans) { if (root == null) { return 0; } int left = robot(root.left, ans); int right = robot(root.right, ans); // 维护直径最大值 ans[0] = Math.max(left + right, ans[0]); // 返回当前节点的最大直径 return Math.max(left, right) + 1; }
二叉树的坡度
- 二叉树的坡度
给定一个二叉树，计算整个树的坡度。
一个树的节点的坡度定义即为，该节点左子树的结点之和和右子树结点之和的差的绝对值。空结点的的坡度是0。
整个树的坡度就是其所有节点的坡度之和。
示例:
输入: 1 / \ 2 3 输出: 1 解释: 结点的坡度 2 : 0 结点的坡度 3 : 0 结点的坡度 1 : |2-3| = 1 树的坡度 : 0 + 0 + 1 = 1
注意:
- 任何子树的结点的和不会超过32位整数的范围。
- 坡度的值不会超过32位整数的范围。
public int findTilt(TreeNode root) { int[] ans = new int[1]; robot(root, ans); return ans[0]; } private int robot(TreeNode root, int[] ans) { if (root == null) { return 0; } int left = robot(root.left, ans); int right = robot(root.right, ans); ans[0] += Math.abs(left - right); return left + right + root.val; }
二叉树的所有路径
- 二叉树的所有路径
给定一个二叉树，返回所有从根节点到叶子节点的路径。
说明: 叶子节点是指没有子节点的节点。
示例:
输入: 1 / \ 2 3 \ 5 输出: ["1->2->5", "1->3"] 解释: 所有根节点到叶子节点的路径为: 1->2->5, 1->3
public List<String> binaryTreePaths(TreeNode root) { List<String> ans = new ArrayList<>(); robot(root, ans, ""); return ans; } private void robot(TreeNode root, List<String> ans, String path) { if (root == null) { return; } if (root.left == null && root.right == null) { ans.add(path + root.val); return; } robot(root.left, ans, path + root.val + "->"); robot(root.right, ans, path + root.val + "->"); }
二叉树的最近公共祖先
- 二叉树的最近公共祖先
给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。
百度百科中最近公共祖先的定义为：“对于有根树 T 的两个结点 p、q，最近公共祖先表示为一个结点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”
例如，给定如下二叉树: root = [3,5,1,6,2,0,8,null,null,7,4]
示例 1:
输入: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1 输出: 3 解释: 节点 5 和节点 1 的最近公共祖先是节点 3。
示例 2:
输入: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4 输出: 5 解释: 节点 5 和节点 4 的最近公共祖先是节点 5。因为根据定义最近公共祖先节点可以为节点本身。
说明:
- 所有节点的值都是唯一的。
- p、q 为不同节点且均存在于给定的二叉树中。
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 root; } return left == null ? right : left; }
最深叶节点的最近公共祖先
- 最深叶节点的最近公共祖先
给你一个有根节点的二叉树，找到它最深的叶节点的最近公共祖先。
回想一下：
- 叶节点 是二叉树中没有子节点的节点
- 树的根节点的 深度 为 0，如果某一节点的深度为 d，那它的子节点的深度就是 d+1
- 如果我们假定 A 是一组节点 S 的 最近公共祖先 中的每个节点都在以 A 为根节点的子树中，且 A 的深度达到此条件下可能的最大值。
示例 1：
输入：root = [1,2,3] 输出：[1,2,3]
示例 2：
输入：root = [1,2,3,4] 输出：[4]
示例 3：
输入：root = [1,2,3,4,5] 输出：[2,4,5]
提示：
- 给你的树中将有 1 到 1000 个节点。
- 树中每个节点的值都在 1 到 1000 之间。
public TreeNode lcaDeepestLeaves(TreeNode root) { if (root == null) { return null; } int left = depth(root.left); int right = depth(root.right); if (left == right) { return root; } return left > right ? lcaDeepestLeaves(root.left) : lcaDeepestLeaves(root.right); } private int depth(TreeNode root) { if (root == null) { return 0; } int left = depth(root.left); int right = depth(root.right); return Math.max(left, right) + 1; }
路径和
左叶子之和
- 左叶子之和
计算给定二叉树的所有左叶子之和。
示例：
3 / \ 9 20 / \ 15 7
在这个二叉树中，有两个左叶子，分别是 9 和 15，所以返回 24
public int sumOfLeftLeaves(TreeNode root) { int[] ans = new int[1]; robot(root, ans, false); return ans[0]; } private void robot(TreeNode root, int[] ans, boolean isLeft) { if (root == null) { return; } if (root.left == null && root.right == null && isLeft) { ans[0] += root.val; } robot(root.left, ans, true); robot(root.right, ans, false); }
路径总和
- 路径总和
给定一个二叉树和一个目标和，判断该树中是否存在根节点到叶子节点的路径，这条路径上所有节点值相加等于目标和。
说明: 叶子节点是指没有子节点的节点。
示例:
给定如下二叉树，以及目标和 sum = 22，
5 / \ 4 8 / / \ 11 13 4 / \ \ 7 2 1
返回 true, 因为存在目标和为 22 的根节点到叶子节点的路径 5->4->11->2。
public boolean hasPathSum(TreeNode root, int sum) { if (root == null) { return false; } // 叶子节点 && 和为 sum if (root.left == null && root.right == null && sum - root.val == 0) { return true; } return hasPathSum(root.left, sum - root.val) || hasPathSum(root.right, sum - root.val); }
路径总和 II
- 路径总和 II
给定一个二叉树和一个目标和，找到所有从根节点到叶子节点路径总和等于给定目标和的路径。
说明: 叶子节点是指没有子节点的节点。
示例:
给定如下二叉树，以及目标和 sum = 22，
5 / \ 4 8 / / \ 11 13 4 / \ / \ 7 2 5 1
返回:
[ [5,4,11,2], [5,8,4,5] ]
public List<List<Integer>> pathSum(TreeNode root, int sum) { List<List<Integer>> ans = new ArrayList<>(); robot(root, sum, ans, new ArrayList<>()); return ans; } private void robot(TreeNode root, int sum, List<List<Integer>> ans, List<Integer> tmp) { if (root == null) { return; } tmp.add(root.val); if (root.left == null && root.right == null && sum == root.val) { ans.add(new ArrayList(tmp)); tmp.remove(tmp.size() - 1); return; } robot(root.left, sum - root.val, ans, tmp); robot(root.right, sum - root.val, ans, tmp); tmp.remove(tmp.size() - 1); }
路径总和 III
- 路径总和 III
给定一个二叉树，它的每个结点都存放着一个整数值。
找出路径和等于给定数值的路径总数。
路径不需要从根节点开始，也不需要在叶子节点结束，但是路径方向必须是向下的（只能从父节点到子节点）。
二叉树不超过1000个节点，且节点数值范围是 [-1000000,1000000] 的整数。
示例：
root = [10,5,-3,3,2,null,11,3,-2,null,1], sum = 8
10 / \ 5 -3 / \ \ 3 2 11 / \ \ 3 -2 1
返回 3。和等于 8 的路径有:
1. 5 -> 3 2. 5 -> 2 -> 1 3. -3 -> 11
public int pathSum(TreeNode root, int sum) { if (root == null) { return 0; } return robot(root, sum) + pathSum(root.left, sum) + pathSum(root.right, sum); } private int robot(TreeNode root, int sum) { if (root == null) { return 0; } int ans = 0; sum -= root.val; if (sum == 0) { ans++; } ans += robot(root.left, sum); ans += robot(root.right, sum); return ans; }
二叉树中的最大路径和
- 二叉树中的最大路径和
给定一个非空二叉树，返回其最大路径和。
本题中，路径被定义为一条从树中任意节点出发，达到任意节点的序列。该路径至少包含一个节点，且不一定经过根节点。
示例 1:
输入: [1,2,3] 1 / \ 2 3 输出: 6
示例 2:
输入: [-10,9,20,null,null,15,7] -10 / \ 9 20 / \ 15 7 输出: 42
public int maxPathSum(TreeNode root) { int[] ans = new int[] { Integer.MIN_VALUE }; robot(root, ans); return ans[0]; } private int robot(TreeNode root, int[] ans) { if (root == null) { return 0; } int left = robot(root.left, ans); int right = robot(root.right, ans); int res = root.val; if (Math.max(left, right) > 0) { res += Math.max(left, right); } int gain = Math.max(Math.max(left, right), left + right); ans[0] = Math.max(ans[0], root.val); ans[0] = Math.max(ans[0], root.val + gain); return res; }
求根到叶子节点数字之和
- 求根到叶子节点数字之和
给定一个二叉树，它的每个结点都存放一个 0-9 的数字，每条从根到叶子节点的路径都代表一个数字。
例如，从根到叶子节点路径 1->2->3 代表数字 123。
计算从根到叶子节点生成的所有数字之和。
说明: 叶子节点是指没有子节点的节点。
示例 1:
输入: [1,2,3] 1 / \ 2 3 输出: 25 解释: 从根到叶子节点路径 1->2 代表数字 12. 从根到叶子节点路径 1->3 代表数字 13. 因此，数字总和 = 12 + 13 = 25.
示例 2:
输入: [4,9,0,5,1] 4 / \ 9 0 / \ 5 1 输出: 1026 解释: 从根到叶子节点路径 4->9->5 代表数字 495. 从根到叶子节点路径 4->9->1 代表数字 491. 从根到叶子节点路径 4->0 代表数字 40. 因此，数字总和 = 495 + 491 + 40 = 1026.
public int sumNumbers(TreeNode root) { return robot(root, 0); } private int robot(TreeNode root, int p) { if (root == null) { return 0; } p = p * 10 + root.val; if (root.left == null && root.right == null) { return p; } return robot(root.left, p) + robot(root.right, p); }
序列化二叉树、构造二叉树
从前序与中序遍历序列构造二叉树
- 从前序与中序遍历序列构造二叉树
根据一棵树的前序遍历与中序遍历构造二叉树。
注意:
你可以假设树中没有重复的元素。
例如，给出
前序遍历 preorder = [3,9,20,15,7] 中序遍历 inorder = [9,3,15,20,7]
返回如下的二叉树：
3 / \ 9 20 / \ 15 7
public TreeNode buildTree(int[] pre, int[] in) { return robot(pre, in, 0, 0, in.length - 1); } private TreeNode robot(int[] pre, int[] in, int preStart, int inStart, int inEnd) { if (preStart >= pre.length || inStart > inEnd) { return null; } // 找到pos TreeNode root = new TreeNode(pre[preStart]); int index = 0; for (int i = inStart; i <= inEnd; i++) { if (in[i] == root.val) { index = i; break; } } root.left = robot(pre, in, preStart + 1, inStart, index - 1); root.right = robot(pre, in, preStart + 1 + index - inStart, index + 1, inEnd); return root; }
从中序与后序遍历序列构造二叉树
- 从中序与后序遍历序列构造二叉树
根据一棵树的中序遍历与后序遍历构造二叉树。
注意:
你可以假设树中没有重复的元素。
例如，给出
中序遍历 inorder = [9,3,15,20,7] 后序遍历 postorder = [9,15,7,20,3]
返回如下的二叉树：
3 / \ 9 20 / \ 15 7
public TreeNode buildTree(int[] in, int[] post) { return robot(in, post, 0, in.length - 1, 0, post.length - 1); } private TreeNode robot(int[] in, int[] post, int inStart, int inEnd, int postStart, int postEnd) { if (postStart > postEnd) { return null; } TreeNode root = new TreeNode(post[postEnd]); int pos = 0; // 找到pos for (int i = inStart; i <= inEnd; i++) { if (in[i] == root.val) { pos = i; break; } } root.left = robot(in, post, inStart, pos - 1, postStart, postStart + pos - inStart - 1); root.right = robot(in, post, pos + 1, inEnd, postEnd + pos - inEnd, postEnd - 1); return root; }
先序遍历构造二叉树
- 先序遍历构造二叉树
返回与给定先序遍历 preorder 相匹配的二叉搜索树（binary search tree）的根结点。
(回想一下，二叉搜索树是二叉树的一种，其每个节点都满足以下规则，对于 node.left 的任何后代，值总 < node.val，而 node.right 的任何后代，值总 > node.val。此外，先序遍历首先显示节点的值，然后遍历 node.left，接着遍历 node.right。）
示例：
输入：[8,5,1,7,10,12] 输出：[8,5,10,1,7,null,12]
提示：
- 1 <= preorder.length <= 100
- 先序 preorder 中的值是不同的。
int index = 0; public TreeNode bstFromPreorder(int[] preorder) { return robot(preorder, Integer.MIN_VALUE, Integer.MAX_VALUE); } private TreeNode robot(int[] preorder, int min, int max) { if (index == preorder.length) { return null; } int val = preorder[index]; if (val < min || val > max) { return null; } index++; TreeNode root = new TreeNode(val); root.left = robot(preorder, min, val); root.right = robot(preorder, val, max); return root; }
序列化和反序列化二叉搜索树
- 序列化和反序列化二叉搜索树
序列化是将数据结构或对象转换为一系列位的过程，以便它可以存储在文件或内存缓冲区中，或通过网络连接链路传输，以便稍后在同一个或另一个计算机环境中重建。
设计一个算法来序列化和反序列化二叉搜索树。 对序列化/反序列化算法的工作方式没有限制。 您只需确保二叉搜索树可以序列化为字符串，并且可以将该字符串反序列化为最初的二叉搜索树。
编码的字符串应尽可能紧凑。
注意：不要使用类成员/全局/静态变量来存储状态。 你的序列化和反序列化算法应该是无状态的。
public class Codec { // Encodes a tree to a single string. // BST 的前序遍历 public String serialize(TreeNode root) { if (root == null) { return ""; } StringBuilder sb = new StringBuilder(); robot(root, sb); return sb.substring(0, sb.length() - 1); } private void robot(TreeNode root, StringBuilder sb) { if (root == null) { return; } sb.append(root.val).append(","); robot(root.left, sb); robot(root.right, sb); } // Decodes your encoded data to tree. public TreeNode deserialize(String data) { if (data == null || Objects.equals(data, "")) { return null; } String[] pre = data.split(","); return build(pre, 0, pre.length - 1); } private TreeNode build(String[] pre, int start, int end) { if (start > end) { return null; } TreeNode root = new TreeNode(Integer.valueOf(pre[start])); // 找到对应的 index int index = end + 1; for (int i = start + 1; i <= end; i++) { if (Integer.valueOf(pre[i]) > root.val) { index = i; break; } } root.left = build(pre, start + 1, index - 1); root.right = build(pre, index, end); return root; } } // Your Codec object will be instantiated and called as such: // Codec codec = new Codec(); // codec.deserialize(codec.serialize(root));
二叉树的序列化与反序列化
- 二叉树的序列化与反序列化
序列化是将一个数据结构或者对象转换为连续的比特位的操作，进而可以将转换后的数据存储在一个文件或者内存中，同时也可以通过网络传输到另一个计算机环境，采取相反方式重构得到原数据。
请设计一个算法来实现二叉树的序列化与反序列化。这里不限定你的序列 / 反序列化算法执行逻辑，你只需要保证一个二叉树可以被序列化为一个字符串并且将这个字符串反序列化为原始的树结构。
示例:
你可以将以下二叉树： 1 / \ 2 3 / \ 4 5 序列化为 "[1,2,3,null,null,4,5]"
提示: 这与 LeetCode 目前使用的方式一致，详情请参阅 LeetCode 序列化二叉树的格式。你并非必须采取这种方式，你也可以采用其他的方法解决这个问题。
说明: 不要使用类的成员 / 全局 / 静态变量来存储状态，你的序列化和反序列化算法应该是无状态的。
public String serialize(TreeNode root) { if (root == null) { return ""; } StringBuilder sb = new StringBuilder(); Deque<TreeNode> deque = new LinkedList<>(); deque.add(root); while (!deque.isEmpty()) { TreeNode p = deque.pop(); if (p == null) { sb.append(",#"); } else { sb.append(",").append(p.val); deque.add(p.left); deque.add(p.right); } } return sb.toString().substring(1); } public TreeNode deserialize(String data) { if (data == null || Objects.equals(data, "")) { return null; } String[] s = data.split(","); TreeNode[] root = new TreeNode[s.length]; for (int i = 0; i < root.length; i++) { if (!Objects.equals(s[i], "#")) { root[i] = new TreeNode(Integer.valueOf(s[i])); } } int parent = 0; for (int i = 0; parent * 2 + 2 < s.length; i++) { if (root[i] != null) { root[i].left = root[parent * 2 + 1]; root[i].right = root[parent * 2 + 2]; parent++; } } return root[0]; }
情绪很多言语又有限
