递归处理
104. 二叉树的最大深度
难度：简单
给定一个二叉树，找出其最大深度。
二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。
说明: 叶子节点是指没有子节点的节点。
示例：
给定二叉树 [3,9,20,null,null,15,7]，
3
/ \
9 20
/ \
15 7
返回它的最大深度 3 。
二叉树的最大深度 = max(左子树最大深度, 右子树最大深度) + 1
public int maxDepth(TreeNode root) {
if (root == null) {
return 0;
} else {
int left_height = maxDepth(root.left);
int right_height = maxDepth(root.right);
return Math.max(left_height, right_height) + 1;
}
}
110. 平衡二叉树
难度：简单
给定一个二叉树，判断它是否是高度平衡的二叉树。
本题中，一棵高度平衡二叉树定义为：
一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过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 。
利用求树的深度的方法，和一个全局变量，所有节点的左右子树高度差都小于等于 1 时，整棵树才是平衡树。
private boolean result = true;
public boolean isBalanced (TreeNode root) {
maxDepth(root);
return result;
}
private int maxDepth (TreeNode root) {
if (root == null) {
return 0;
}
int l = maxDepth(root.left);
int r = maxDepth(root.right);
if (Math.abs(l - r) > 1) result = false;
return Math.max(l, r) + 1;
}
543. 二叉树的直径
难度：简单
给定一棵二叉树，你需要计算它的直径长度。一棵二叉树的直径长度是任意两个结点路径长度中的最大值。这条路径可能穿过根结点。
示例 :
给定二叉树
1
/ \
2 3
/ \
4 5
返回 3, 它的长度是路径 [4,2,1,3] 或者 [5,2,1,3]。
注意：两结点之间的路径长度是以它们之间边的数目表示。
求二叉树的直径，实际上就是求所有节点中，左子树的深度+右子树的深度 的最大值。
private int longestPath = 0;
public int diameterOfBinaryTree (TreeNode root) {
depth(root);
return longestPath;
}
private int depth (TreeNode root) {
if (root == null) {
return 0;
}
int l = depth(root.left);
int r = depth(root.right);
longestPath = Math.max(longestPath, l + r);
return Math.max(l, r) + 1;
}
226. 翻转二叉树
难度：简单
翻转一棵二叉树。
示例：
输入：
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 left = root.left; // 后面的操作会改变 left 指针，因此先保存下来
root.left = invertTree(root.right);
root.right = invertTree(left);
return root;
}
617. 合并二叉树
难度：简单
给定两个二叉树，想象当你将它们中的一个覆盖到另一个上时，两个二叉树的一些节点便会重叠。
你需要将他们合并为一个新的二叉树。合并的规则是如果两个节点重叠，那么将他们的值相加作为节点合并后的新值，否则不为 NULL 的节点将直接作为新二叉树的节点。
示例 1:
输入:
Tree 1 Tree 2
1 2
/ \ / \
3 2 1 3
/ \ \
5 4 7
输出:
合并后的树:
3
/ \
4 5
/ \ \
5 4 7
注意: 合并必须从两个树的根节点开始。
新建一个节点，用来保存两棵树相同位置的节点的和。
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 treeNode = new TreeNode(t1.val + t2.val);
treeNode.left = mergeTrees(t1.left, t2.left);
treeNode.right = mergeTrees(t1.right, t2.right);
return treeNode;
}
112. 路径总和
难度：简单
给定一个二叉树和一个目标和，判断该树中是否存在根节点到叶子节点的路径，这条路径上所有节点值相加等于目标和。
说明: 叶子节点是指没有子节点的节点。
示例:
给定如下二叉树，以及目标和 sum = 22，
5
/ \
4 8
/ / \
11 13 4
/ \ \
7 2 1
返回 true, 因为存在目标和为 22 的根节点到叶子节点的路径 5->4->11->2。
每往下一层，目标的值就要减去当前的节点。注意题目条件是根节点到叶子节点的路径，所以返回 true 的判断条件里要加上是否为叶子节点的判断。
public boolean hasPathSum (TreeNode root, int sum) {
if (root == null) {
return false;
}
if (root.left == null && root.right == null && root.val == sum) {
return true;
}
return hasPathSum(root.left, sum - root.val) || hasPathSum(root.right, sum - root.val);
}
437. 路径总和 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
使用一个辅助函数pathSumStartWithNode，表示以一个节点开始，路径和等于目标值的路径数量。
整棵树的符合条件的路径数量就是以根节点开头的路径数量+以左右子树开头的路径数量（注意用的方法不一样，左右子树需要递归）
public int pathSum (TreeNode root, int sum) {
if (root == null) {
return 0;
}
return pathSumStartWithNode(root, sum)
+ pathSum(root.left, sum)
+ pathSum(root.right, sum);
}
private int pathSumStartWithNode (TreeNode node, int sum) {
if (node == null) {
return 0;
}
int ans = 0;
if (node.val == sum) ans++;
ans += pathSumStartWithNode(node.left, sum - node.val)
+ pathSumStartWithNode(node.right, sum - node.val);
return ans;
}
572. 另一个树的子树
难度：简单
给定两个非空二叉树 s 和 t，检验 s 中是否包含和 t 具有相同结构和节点值的子树。s 的一个子树包括 s 的一个节点和这个节点的所有子孙。s 也可以看做它自身的一棵子树。
示例 1:
给定的树 s:
3
/ \
4 5
/ \
1 2
给定的树 t：
4
/ \
1 2
返回 true，因为 t 与 s 的一个子树拥有相同的结构和节点值。
示例 2:
给定的树 s：
3
/ \
4 5
/ \
1 2
/
0
给定的树 t：
4
/ \
1 2
返回 false。
使用一个辅助函数isSubtreeWithRoot，（递归地）判断两棵子树是不是相等的。
然后利用和437. 路径总和 III类似的思想，看以根节点开头能匹配吗，以根节点的左右子树开头能匹配吗，同样要注意用的方法不一样，左右子树的判断需要递归处理。
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 (s == null && t == null) return true;
if (s == null || t == null) return false;
if (s.val != t.val) return false;
return isSubtreeWithRoot(s.left, t.left) && isSubtreeWithRoot(s.right, t.right);
}
101. 对称二叉树
难度：简单
给定一个二叉树，检查它是否是镜像对称的。
例如，二叉树 [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 isSymmetric(root,root);
}
private boolean isSymmetric(TreeNode t1, TreeNode t2) {
if (t1 == null && t2 == null){
return true;
}
if (t1 == null || t2 == null){
return false;
}
return t1.val == t2.val &&
isSymmetric(t1.left, t2.right) &&
isSymmetric(t1.right, t2.left);
}
111. 二叉树的最小深度
难度：简单
给定一个二叉树，找出其最小深度。
最小深度是从根节点到最近叶子节点的最短路径上的节点数量。
说明: 叶子节点是指没有子节点的节点。
示例:
给定二叉树 [3,9,20,null,null,15,7],
3
/ \
9 20
/ \
15 7
返回它的最小深度 2.
二叉树的最小深度 = min(左子树最小深度, 右子树最小深度) + 1
跟最大深度处理不同的是，碰叶左子树或者右子树深度是 0 的时候，就要计算当前节点的深度，不然使用min(左子树最小深度, 右子树最小深度) + 1会出现错误的结果。比如[1,2]。
public int minDepth(TreeNode root) {
if (root == null) {
return 0;
}
int leftDepth = minDepth(root.left);
int rightDepth = minDepth(root.right);
if (leftDepth == 0 || rightDepth == 0) {
return leftDepth + rightDepth + 1;
}
return Math.min(leftDepth,rightDepth) + 1;
}
404. 左叶子之和
难度：简单
计算给定二叉树的所有左叶子之和。
示例：
3
/ \
9 20
/ \
15 7
在这个二叉树中，有两个左叶子，分别是 9 和 15，所以返回 24
首先要使用一个辅助函数isLeaf来判断一个节点是不是叶子节点。
在一棵树中从根节点开始寻找，
如果一个节点的左子节点是叶子节点，就返回左子节点的值 + 右子树中左叶子的和；
如果不是，就继续在左右子节点中寻找求和。
public int sumOfLeftLeaves(TreeNode root) {
if (root == null) {
return 0;
}
if (isLeaf(root.left)) {
return root.left.val + sumOfLeftLeaves(root.right);
}
return sumOfLeftLeaves(root.left) + sumOfLeftLeaves(root.right);
}
private boolean isLeaf (TreeNode root) {
if (root == null) {
return false;
}
return root.left == null && root.right == null;
}
687. 最长同值路径
难度：简单
给定一个二叉树，找到最长的路径，这个路径中的每个节点具有相同值。 这条路径可以经过也可以不经过根节点。
注意：两个节点之间的路径长度由它们之间的边数表示。
示例 1:
输入:
输入：
5
/ \
4 5
/ \ \
1 1 5
输出：
2
示例 2:
输入:
输入：
1
/ \
4 5
/ \ \
4 4 5
输出：
2
注意: 给定的二叉树不超过10000个结点。 树的高度不超过1000。
令 arrow_length(node) 为从节点 node 延伸出的最长箭头的长度。如果 node.Left 存在且与节点 node 具有相同的值，则该值就会是 1 + arrow_length(node.left)。在 node.right 存在的情况下也是一样。
当我们计算箭头长度时，候选答案将是该节点在两个方向上的箭头之和。我们将这些候选答案记录下来，并返回最佳答案。
作者：LeetCode
链接：https://leetcode-cn.com/problems/two-sum/solution/zui-chang-tong-zhi-lu-jing-by-leetcode/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
private int longestPath;
public int longestUnivaluePath(TreeNode root) {
arrowLength(root);
return longestPath;
}
private int arrowLength (TreeNode root) {
if (root == null) {
return 0;
}
int left = arrowLength(root.left);
int right = arrowLength(root.right);
int leftArrowLength = root.left != null && root.left.val == root.val ? left + 1 : 0;
int rightArrowLength = root.right != null && root.right.val == root.val ? right + 1 : 0;
longestPath = Math.max(leftArrowLength + rightArrowLength, longestPath);
return Math.max(leftArrowLength, rightArrowLength);
}
337. 打家劫舍 III
难度：中等
在上次打劫完一条街道之后和一圈房屋后，小偷又发现了一个新的可行窃的地区。这个地区只有一个入口，我们称之为“根”。 除了“根”之外，每栋房子有且只有一个“父“房子与之相连。一番侦察之后，聪明的小偷意识到“这个地方的所有房屋的排列类似于一棵二叉树”。 如果两个直接相连的房子在同一天晚上被打劫，房屋将自动报警。
计算在不触动警报的情况下，小偷一晚能够盗取的最高金额。
示例 1:
输入: [3,2,3,null,3,null,1]
3
/ \
2 3
\ \
3 1
输出: 7
解释: 小偷一晚能够盗取的最高金额 = 3 + 3 + 1 = 7.
示例 2:
输入: [3,4,5,1,3,null,1]
3
/ \
4 5
/ \ \
1 3 1
输出: 9
解释: 小偷一晚能够盗取的最高金额 = 4 + 5 = 9.
从根节点开始，要么就偷下一层的（左右节点），要么就偷左/右节点的下层。
public int rob(TreeNode root) {
if (root == null) {
return 0;
}
int var1 = root.val;
if (root.left != null) {
var1 += rob(root.left.left) + rob(root.left.right);
}
if (root.right != null) {
var1 += rob(root.right.left) + rob(root.right.right);
}
int var2 = rob(root.left) + rob(root.right);
return Math.max(var1, var2);
}
671. 二叉树中第二小的节点
难度：简单
给定一个非空特殊的二叉树，每个节点都是正数，并且每个节点的子节点数量只能为 2 或 0。如果一个节点有两个子节点的话，那么这个节点的值不大于它的子节点的值。
给出这样的一个二叉树，你需要输出所有节点中的第二小的值。如果第二小的值不存在的话，输出 -1 。
示例 1:
输入:
2
/ \
2 5
/ \
5 7
输出: 5
说明: 最小的值是 2 ，第二小的值是 5 。
示例 2:
输入:
2
/ \
2 2
输出: -1
说明: 最小的值是 2, 但是不存在第二小的值。
注意题目条件，每个节点的子节点数量只能为2 或 0，也就是说要么满要么空，且如果是满的话，父节点的值不大于子节点的值。
如果一个节点为空，或者这个节点就是叶子节点，函数直接返回 - 1。
如果子节点中有跟父节点的值相等的，就继续往下找第二小的值；如果子节点中没有跟父节点的值相等的，第二小的值就是子节点中比较小的那个。
public int findSecondMinimumValue(TreeNode root) {
if (root == null) {
return -1;
}
if (root.left == null && root.right == null) {
return -1;
}
int leftVal = root.left.val;
int rightVal = root.right.val;
if (leftVal == root.val) leftVal = findSecondMinimumValue(root.left);
if (rightVal == root.val) rightVal = findSecondMinimumValue(root.right);
if (leftVal != -1 && rightVal != -1) {
return Math.min(leftVal, rightVal);
}
if (leftVal != -1) {
return leftVal;
}
return rightVal;
}
层次遍历
利用队列进行层次遍历
637. 二叉树的层平均值
难度：简单
给定一个非空二叉树, 返回一个由每层节点平均值组成的数组.
示例 1:
输入:
3
/ \
9 20
/ \
15 7
输出: [3, 14.5, 11]
解释:
第0层的平均值是 3, 第1层是 14.5, 第2层是 11. 因此返回 [3, 14.5, 11].
注意：
- 节点值的范围在32位有符号整数范围内。
注意队列的构造方式：Queue<TreeNode> q = new LinkedList<>();
先把根节点加进去，再根据队列的大小，把左右子树入队。
public List<Double> averageOfLevels (TreeNode root) {
Queue<TreeNode> q = new LinkedList<>();
List<Double> ans = new ArrayList<>();
if (root == null)
return ans;
q.add(root);
while (q.size() > 0) {
int s = q.size();
double sum = 0;
for (int i = 0; i < s; i++) {
TreeNode tn = q.remove();
if (tn.left != null) q.add(tn.left);
if (tn.right != null) q.add(tn.right);
sum += tn.val;
}
ans.add(sum / s);
}
return ans;
}
513. 找树左下角的值
难度：简单
给定一个二叉树，在树的最后一行找到最左边的值。
示例 1:
输入:
2
/ \
1 3
输出:
1
示例 2:
输入:
1
/ \
2 3
/ / \
4 5 6
/
7
输出:
7
注意: 您可以假设树（即给定的根节点）不为 NULL。
注意队列的构造方式：Queue<TreeNode> q = new LinkedList<>();
先把根节点加进去，再先把右子树入队，左子树入队（遍历顺序类似于中-右-左），最后一个出队的节点就是左下角的节点了。
public int findBottomLeftValue(TreeNode root) {
Queue<TreeNode> queue = new LinkedList<>();
queue.add(root);
while (!queue.isEmpty()) {
root = queue.poll();
if (root.right != null) {
queue.add(root.right);
}
if (root.left != null) {
queue.add(root.left);
}
}
return root.val;
}
前中后序遍历
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 实现。
前序、中序、后序遍只是在对节点访问的顺序有一点不同，其它都相同。
非递归实现二叉树的前序遍历
144. 二叉树的前序遍历
难度：中等
给定一个二叉树，返回它的 前序 遍历。
示例:
输入: [1,null,2,3]
1
\
2
/
3
输出: [1,2,3]
进阶: 递归算法很简单，你可以通过迭代算法完成吗？
递归法：
public List<Integer> preorderTraversal(TreeNode root) {
List<Integer> res = new ArrayList<>();
helper(root, res);
return res;
}
private void helper(TreeNode root, List<Integer> res) {
if (root == null) return;
res.add(root.val);
helper(root.left, res);
helper(root.right, res);
}
迭代法：
利用栈，注意左右节点入栈时的顺序
public List<Integer> preorderTraversal (TreeNode root) {
List<Integer> ans = new ArrayList<>();
Stack<TreeNode> stack = new Stack<>();
stack.push(root);
while (!stack.isEmpty()) {
TreeNode node = stack.pop();
if (node == null) {
continue;
}
ans.add(node.val);
stack.push(node.right);
stack.push(node.left);
}
return ans;
}
非递归实现二叉树的后序遍历
145. 二叉树的后序遍历
难度：中等
给定一个二叉树，返回它的 后序 遍历。
示例:
输入: [1,null,2,3]
1
\
2
/
3
输出: [3,2,1]
进阶: 递归算法很简单，你可以通过迭代算法完成吗？
递归法：
public List<Integer> postorderTraversal(TreeNode root) {
List<Integer> res = new ArrayList<>();
helper(root, res);
return res;
}
private void helper(TreeNode root, List<Integer> res) {
if (root == null) return;
helper(root.left, res);
helper(root.right, res);
res.add(root.val);
}
迭代法：
利用栈，前序遍历的顺序为根左右，后序遍历为左右根，可以改造前序遍历，变为根右左，再反向输出。
public List<Integer> postorderTraversal (TreeNode root) {
List<Integer> ans = new ArrayList<>();
Stack<TreeNode> stack = new Stack<>();
stack.push(root);
while (!stack.isEmpty()) {
TreeNode node = stack.pop();
if (node == null) {
continue;
}
ans.add(node.val);
stack.push(node.left);
stack.push(node.right);
}
Collections.reverse(ans);
return ans;
}
非递归实现二叉树的中序遍历
94. 二叉树的中序遍历
难度：中等
给定一个二叉树，返回它的中序 遍历。
示例:
输入: [1,null,2,3]
1
\
2
/
3
输出: [1,3,2]
进阶: 递归算法很简单，你可以通过迭代算法完成吗？
递归法：
public List<Integer> inorderTraversal(TreeNode root) {
List<Integer> res = new ArrayList<>();
helper(root, res);
return res;
}
private void helper(TreeNode root, List<Integer> res) {
if (root == null) return;
helper(root.left, res);
res.add(root.val);
helper(root.right, res);
}
迭代法：
利用栈。因为根节点是放在中间的，所以不能像前序遍历那样简单粗暴地用栈了。
public List<Integer> inorderTraversal(TreeNode root) {
List<Integer> ans = new ArrayList<>();
Stack<TreeNode> stack = new Stack<>();
if (root == null) {
return ans;
}
TreeNode cur = root;
while (cur != null || !stack.isEmpty()) {
while (cur != null) {
stack.push(cur);
cur = cur.left;
}
TreeNode node = stack.pop();
ans.add(node.val);
cur = node.right;
}
return ans;
}
BST
669. 修剪二叉搜索树
难度：简单
给定一个二叉搜索树，同时给定最小边界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;
}
230. 二叉搜索树中第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 函数？
根据二叉树的特性，一个节点的左子树是都小于这个节点的，所以可以根据左子树的大小来判断当前节点在整棵树中是第几位。
public int kthSmallest (TreeNode root, int k) {
int t = size(root.left);
if (t > k-1) return kthSmallest(root.left,k);
else if (t < k-1) return kthSmallest(root.right, k - t -1);
else return root.val;
}
private int size (TreeNode root) {
if (root == null) return 0;
return size(root.left) + size(root.right) + 1;
}
利用中序遍历：
private int cnt = 0;
private int val;
public int kthSmallest(TreeNode root, int k) {
inOrder(root, k);
return val;
}
private void inOrder(TreeNode node, int k) {
if (node == null) return;
inOrder(node.left, k);
cnt++;
if (cnt == k) {
val = node.val;
return;
}
inOrder(node.right, k);
}
538. 把二叉搜索树转换为累加树
难度：简单
给定一个二叉搜索树（Binary Search Tree），把它转换成为累加树（Greater Tree)，使得每个节点的值是原来的节点值加上所有大于它的节点值之和。
例如：
输入: 二叉搜索树:
5
/ \
2 13
输出: 转换为累加树:
18
/ \
20 13
采用类似中序遍历的方法，但是访问顺序是右-中-左，相当于把树从大到小遍历，把每次访问的节点的值累加起来。
int sum = 0;
public TreeNode convertBST (TreeNode root) {
traver(root);
return root;
}
private void traver (TreeNode node) {
if (node == null) {
return;
}
traver(node.right);
sum += node.val;
node.val = sum;
traver(node.left);
}
235. 二叉搜索树的最近公共祖先
难度：简单
给定一个二叉搜索树, 找到该树中两个指定节点的最近公共祖先。
百度百科中最近公共祖先的定义为：“对于有根树 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 为不同节点且均存在于给定的二叉搜索树中。
注意题目，给的条件是二叉搜索树。
遍历BST
如果当前访问的节点的值大于给定的两个节点，说明p,q都在当前节点的左子树，则继续往左子树搜索；
如果当前访问的节点的值小于给定的两个节点，说明p,q都在当前节点的右子树，则继续往左子树搜索；
那就只剩一种情况了，当前访问的节点的值正好在 p,q 之间，则最近公共祖先就是当前节点。
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
if (root.val > p.val && root.val > q.val) return lowestCommonAncestor(root.left, p, q);
if (root.val < p.val && root.val < q.val) return lowestCommonAncestor(root.right, p, q);
return root;
}
236. 二叉树的最近公共祖先
难度：中等
给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。
百度百科中最近公共祖先的定义为：“对于有根树 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 为不同节点且均存在于给定的二叉树中。
使用深度搜索遍历二叉树，如果在当前子树中找不到目标的p,q就将当前子树标记为null
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) {
return right;
} else if (right == null) {
return left;
} else {
return root;
}
}
108. 将有序数组转换为二叉搜索树
难度：简单
将一个按照升序排列的有序数组，转换为一棵高度平衡二叉搜索树。
本题中，一个高度平衡二叉树是指一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1。
示例:
给定有序数组: [-10,-3,0,5,9],
一个可能的答案是：[0,-3,9,-10,null,5]，它可以表示下面这个高度平衡二叉搜索树：
0
/ \
-3 9
/ /
-10 5
注意题目要求，要转换为一棵高度平衡的二叉搜索树，那么就要把正中间的元素当做根节点。
使用一个辅助方法，采用分治的思想，把数组不断二分，构造出一棵平衡二叉搜索树。
public TreeNode sortedArrayToBST(int[] nums) {
if(nums.length == 0) return null;
TreeNode root = put(nums, 0, nums.length-1);
return root;
}
private TreeNode put (int[] nums, int left, int right){
if (left > right)
return null;
int mid = (left + right) / 2;
TreeNode root = new TreeNode(nums[mid]);
root.left = put(nums,left,mid - 1);
root.right = put(nums, mid + 1, right);
return root;
}
109. 有序链表转换二叉搜索树
难度：中等
给定一个单链表，其中的元素按升序排序，将其转换为高度平衡的二叉搜索树。
本题中，一个高度平衡二叉树是指一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1。
示例:
给定的有序链表： [-10, -3, 0, 5, 9],
一个可能的答案是：[0, -3, 9, -10, null, 5], 它可以表示下面这个高度平衡二叉搜索树：
0
/ \
-3 9
/ /
-10 5
先用一个方法获取链表的长度。然后将结合分治思想和中序遍历构造 BST。
注意：头节点要设置成全局变量，不然在辅助函数的递归中会出错。
private ListNode head;
public TreeNode sortedListToBST(ListNode head) {
int size = getSize(head);
this.head = head;
return convertListNode2BST( 0, size - 1);
}
private TreeNode convertListNode2BST (int l, int r) {
if (l > r) {
return null;
}
int mid = (l + r) / 2;
TreeNode left = convertListNode2BST( l, mid - 1);
TreeNode node = new TreeNode(head.val);
node.left = left;
head = head.next;
node.right = convertListNode2BST( mid + 1, r);
return node;
}
private int getSize (ListNode head) {
ListNode node = head;
int size = 0;
while (node != null) {
node = node.next;
size++;
}
return size;
}
653. 两数之和 IV - 输入 BST
难度：简单
给定一个二叉搜索树和一个目标结果，如果 BST 中存在两个元素且它们的和等于给定的目标结果，则返回 true。
案例 1:
输入:
5
/ \
3 6
/ \ \
2 4 7
Target = 9
输出: True
案例 2:
输入:
5
/ \
3 6
/ \ \
2 4 7
Target = 28
输出: False
先将BST 通过中序遍历转换成一个有序的集合，然后使用双指针，一头一尾查找目标和。
public boolean findTarget(TreeNode root, int k) {
List<Integer> nums = new ArrayList<>();
inorder(root, nums);
int l = 0, r = nums.size() - 1;
while (l < r) {
int sum = nums.get(l) + nums.get(r);
if (sum < k) {
l++;
} else if (sum > k) {
r--;
} else {
return true;
}
}
return false;
}
private void inorder (TreeNode root, List<Integer> nums) {
if (root == null) {
return;
}
inorder(root.left, nums);
nums.add(root.val);
inorder(root.right, nums);
}
530. 二叉搜索树的最小绝对差
难度：简单
给定一个所有节点为非负值的二叉搜索树，求树中任意两节点的差的绝对值的最小值。
示例 :
输入:
1
\
3
/
2
输出:
1
解释:
最小绝对差为1，其中 2 和 1 的差的绝对值为 1（或者 2 和 3）。
注意: 树中至少有2个节点。
用中序遍历这棵二叉树，二叉树中任意两个节点的最小绝对差，肯定在前后挨着的两个节点中产生，这里的前后挨着，不是指在原本的二叉树中是相邻的，而是指使用中序遍历得到的有序集合中是挨着的。
int minDiff = Integer.MAX_VALUE;
TreeNode pre = null;
public int getMinimumDifference (TreeNode root) {
inorder(root);
return minDiff;
}
private void inorder (TreeNode root) {
if (root == null) {
return;
}
inorder(root.left);
if (pre != null) {
minDiff = Math.min(minDiff, root.val - pre.val);
}
pre = root;
inorder(root.right);
}
501. 二叉搜索树中的众数
难度：简单
给定一个有相同值的二叉搜索树（BST），找出 BST 中的所有众数（出现频率最高的元素）。
假定 BST 有如下定义：
- 结点左子树中所含结点的值小于等于当前结点的值
- 结点右子树中所含结点的值大于等于当前结点的值
- 左子树和右子树都是二叉搜索树
例如：
给定 BST [1,null,2,2],
1
\
2
/
2
返回[2].
提示：如果众数超过1个，不需考虑输出顺序
进阶：你可以不使用额外的空间吗？（假设由递归产生的隐式调用栈的开销不被计算在内）
设置一个动态数组nums用来保存出现频率最高的数（可能不止一个）。
中序遍历BST，如果当前节点和上一个节点相等，就把当前计数器curCnt加一，如果当前计数器比最大计数器大了，就更新最大计数器maxCnt，并把动态数组清空，把当前节点放入动态数组，如果当前计数器等于最大计数器了，说明出现了新的众数，放进动态数组里。
最后用一个循环把动态数组转换为数组。
private int curCnt = 1;
private int maxCnt = 1;
TreeNode pre = null;
public int[] findMode(TreeNode root) {
List<Integer> nums = new ArrayList<>();
inorder(root, nums);
int[] ans = new int[nums.size()];
int index = 0;
for (Integer num : nums) {
ans[index++] = num;
}
return ans;
}
private void inorder (TreeNode node, List<Integer> nums) {
if (node == null) {
return;
}
inorder(node.left, nums);
if (pre != null) {
if (pre.val == node.val) curCnt++;
else curCnt = 1;
}
if (curCnt > maxCnt) {
maxCnt = curCnt;
nums.clear();
nums.add(node.val);
} else if (curCnt == maxCnt) {
nums.add(node.val);
}
pre = node;
inorder(node.right, nums);
}
