二叉树经典题目详解（下）

108. 将有序数组转换为二叉搜索树

108. 将有序数组转换为二叉搜索树 - 力扣（LeetCode）

class Solution {public TreeNode sortedArrayToBST(int[] nums) {int len = nums.length;if (len == 0) return null;return build(nums, 0, len - 1);}private TreeNode build(int[] nums, int L, int R) {if (L > R) return null;int mid = L + ((R - L) >> 1);// 当前子树根节点TreeNode treeNode = new TreeNode(nums[mid]);// 构建左右子树treeNode.left = build(nums, L, mid - 1);treeNode.right = build(nums, mid + 1, R);return treeNode;}
}

解题思路：可以将问题拆分成自底向上的构建一个个小子树，每个子树都只构建根节点和左右孩子节点，然后慢慢组装起来。

然后题目也说了是升序的，所以我们可以不断的进行拆分成左右两部分进行处理，左边部分一定是小于右边部分，也就是说左边部分一定是构建左子树，右边部分构建右子树

654.最大二叉树

654. 最大二叉树 - 力扣（LeetCode）

class Solution {public TreeNode constructMaximumBinaryTree(int[] nums) {int len = nums.length;if (len == 0) return null;return build(nums, 0,  len- 1);}private TreeNode build(int[] nums, int L, int R) {if (L > R) return null;// 先找到L到R区域最大的那个元素的下标int maxIndex = getMaxIndex(nums, L, R);// 创建出最大的节点TreeNode treeNode = new TreeNode(nums[maxIndex]);treeNode.left = build(nums, L, maxIndex - 1);treeNode.right = build(nums, maxIndex + 1, R);return treeNode;}private int getMaxIndex(int[] nums, int L, int R) {int maxIndex = L;for (int i = L + 1; i <= R; i++) {if (nums[maxIndex] < nums[i]) maxIndex = i;}return maxIndex;}
}

解题思路：其实这道题和108是一样的，就是有点类似于分治的思想，只不过108是每次找到中间的那个节点，这道题是找到最大的那个节点

我们我们的操作就是不管的在一个范围（L到R）中找到最大的那个节点，然后根据这个节点将这个区间划分成左右两部分，因为从题目可以知道，左边部分最终是要放在左子树的，右边部分最终是放在右子树的

617.合并二叉树

617. 合并二叉树 - 力扣（LeetCode）

class Solution {public TreeNode mergeTrees(TreeNode root1, TreeNode root2) {return build(root1, root2);}private TreeNode build(TreeNode node1, TreeNode node2) {if (node1 == null) return node2;if (node2 == null) return node1;// 进行合并TreeNode treeNode = new TreeNode(node1.val + node2.val);treeNode.left = build(node1.left, node2.left);treeNode.right = build(node1.right, node2.right);return treeNode;}
}

解题思路：这道题就是简单的递归，只需要对root1和root2一起进行递归，然后对遍历到的节点进行判断是要叠加还是只取其中的一个就行

然后像这里不用管node1和node2都是null的情况，因为这种情况也会落到第一个if中，返回node2，相当于返回null

处理完当前遍历到的节点之后就是开始递归处理左右子节点

700.二叉搜索树中的搜索

700. 二叉搜索树中的搜索 - 力扣（LeetCode）

class Solution {public TreeNode searchBST(TreeNode root, int val) {if (root == null) return null;// val小，找左边if (root.val > val) {return searchBST(root.left, val);} // val大，找右边else if (root.val < val) {return searchBST(root.right, val);} // 找到了else {return root;}}
}

解题思路：这道题就是简单的二叉树搜索，每一次递归都有三种情况：

* val小于当前节点的值，找左边

* val大于当前节点的值，找右边

* val等于当前节点的值，返回

530.二叉搜索树的最小绝对差

530. 二叉搜索树的最小绝对差 - 力扣（LeetCode）

class Solution {private int res = Integer.MAX_VALUE;private TreeNode pre = null;public int getMinimumDifference(TreeNode root) {dfs(root);return res;}private void dfs(TreeNode root) {// 没有值if (root == null) return;// 中序遍历// 左dfs(root.left);// 中if (pre != null) {res = Math.min(root.val - pre.val, res);}pre = root;// 右dfs(root.right);}
}

解题思路：这道题的解法其实很好想到，直接拿到所有的节点，然后进行排序，之后不断的进行两两比较相邻节点之间的差值，就能找到最小的那个

那么这个思路如果是放到递归中来实现的话，不想单独开新的容器就可以用中序遍历，因为中序遍历出来的结果本身就是排好序的，然后我们只需要使用到一个变量来记录前一个节点就行了

501.二叉搜索树中的众数

501. 二叉搜索树中的众数 - 力扣（LeetCode）

class Solution {// 我们接下来使用中序遍历的方式，中序遍历的特点就是有序private int base, maxCount, count;private List<Integer> res = new ArrayList<>();public int[] findMode(TreeNode root) {dfs(root);int[] ans = new int[res.size()];for (int i = 0; i < res.size(); i++) {ans[i] = res.get(i);}return ans;}private void dfs(TreeNode node) {if (node == null) return;// 中序遍历        dfs(node.left);update(node.val);dfs(node.right);}private void update(int val) {// 说明不是这一组数字第一次出现if (val == base) {count++;} else {base = val;count = 1;}if (count == maxCount) {res.add(val);}if (count > maxCount) {res.clear();res.add(val);maxCount = count;}}}

解题思路：直接使用中序遍历就行，因为中序遍历出来的结果是有序的，所以我们边遍历边统计每一种数字出现的次数，这样子就能实现找出出现次数最多的那些数字

236. 二叉树的最近公共祖先

236. 二叉树的最近公共祖先 - 力扣（LeetCode）

class Solution {public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {// 遍历每一颗小子树，判断是否包含p q 两个节点return dfs(root, p, q);}private TreeNode dfs(TreeNode node, TreeNode p, TreeNode q) {// 如果当前节点是null的话，就返回null// 如果当前节点是 p q 中的一个的话，就说明当前节点就是公共祖先// （因为如果你继续往下遍历的话必定会漏掉其中的一个，// 或者换个思路，这个操作就是专门用来出来 p 是 q的父节点【反过来一样】的情况，只不过先命中 p 还是先命中 q 的顺序而已）if (node == null || node == p || node == q) return node;// 执行到这里说明 p q 都是在当前节点的孩子节点里面// 找左子树和右子树TreeNode left = dfs(node.left, p, q);TreeNode right = dfs(node.right, p, q);// 如果左右子树都没有，直接返回null，表示找不到（不在当前子树中）if (left == null && right == null) return null;// 在右子树中if (left == null) return right;// 在左子树中if (right == null) return left;// 执行到这里说明不是单纯的在左边或是右边，而是散落在左子树和右子树，直接返回这一轮的节点return node;}
}

解题思路：其实这道题就是要你不断的以每一个节点为根节点的子树，然后判断在这个子树中是否包含 p 和 q 两个节点

那么有5种情况：

1. 当前节点就是p或q中的一个，p是q的父节点【或者反过来】

2. p q 都在当前节点的左孩子中

3. p q 都在当前节点的右孩子中

4. p q 散落在当前节点的左右孩子中

5. p q 不在当前节点的左右孩子中

然后就是针对每一种情况进行判断。

问题：为什么通过node == p || node == q 然后返回node的行为就能找到公共祖先呢？

其实这是由递归的特性决定的，我们是自底向上进行遍历，然后会不断的将信息传递给上层。我们只要判断到其中的一个目标节点就直接返回给上层，让上层去判断另一个节点是在当前子树中还是在其他的子树。（如果还是不理解可以自己模拟一遍）

235. 二叉搜索树的最近公共祖先

235. 二叉搜索树的最近公共祖先 - 力扣（LeetCode）

// code1:
class Solution {public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {while (root != null) {if (p.val < root.val && q.val < root.val) {// 找左边root = root.left;} else if (p.val > root.val && q.val > root.val) {// 找右边root = root.right;} else {// 分叉了，或是当前root节点就是p q 中的一个，直接返回return root;}}// 到这说明没找到return null;}
}// code2:
class Solution {public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {if (root == null) return null;if (p.val < root.val && q.val < root.val) {// 找左边return lowestCommonAncestor(root.left, p, q);} else if (p.val > root.val && q.val > root.val) {// 找右边return lowestCommonAncestor(root.right, p, q);} else {// 分叉了，或是当前root节点就是p q 中的一个，直接返回return root;}}
}

解题思路：这道题其实用236的解法一样适用，但是没必要，因为这个是BST，如果用236的解法的话就没有发挥出这种数据结构的特性。

那么我们这道题的解题思路就是不断进行判断，然后判断是应该往左边找还是往右边找，直到找到分叉或是当前节点就是 p q 中的一个

701.二叉搜索树中的插入操作

701. 二叉搜索树中的插入操作 - 力扣（LeetCode）

class Solution {public TreeNode insertIntoBST(TreeNode root, int val) {// 如果是null说明找到要插入的位置，直接创建一个节点返回就行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;}
}

解题思路：就是不断的判断要插入到左边还是右边，然后我们使用的是插入到叶子节点的方式，所以最后只要判断到 root ==null 就说明已经找到要插入的位置了，直接创建一个节点返回回去就行，然后返回到上一层就实现插入的操作了。

问题：为什么能这样？不会对原本的位置的节点发生改变吗？

答案是不会的，因为这里递归的位置很巧妙，可以发现每一层进来之后进入递归，然后递归出来之后是直接 执行return root 的，因为接下去的代码执行不到。

450.删除二叉搜索树中的节点

450. 删除二叉搜索树中的节点 - 力扣（LeetCode）

class Solution {public TreeNode deleteNode(TreeNode root, int key) {return dfs(root, key);}private TreeNode dfs(TreeNode node, int key) {if (node == null) return null;if (node.val > key) {// 把修改完的子树拼接到当前节点node.left = dfs(node.left, key);} else if (node.val < key) {node.right = dfs(node.right, key);} else {// 判断要删除的节点是什么情况// 如果是一边孩子是null的情况，直接把另一半返回出去拼接就行了if (node.left == null) return node.right;if (node.right == null) return node.left;// 都存在的情况下，就是把右子树的最左边节点找出来，用这个节点替代要删除的节点if (node.left != null && node.right != null) {// 找到右子树的最左节点TreeNode cur = node.right;while (cur.left != null) cur = cur.left;// 找到的这个节点的左孩子直接指向要删除节点的左孩子（因为我们找的是最左边节点。那么它的左孩子肯定是null）// 这一步相当于把要删除的节点的左孩子剪下来接到我们找到的这个节点的左孩子cur.left = node.left;// 要删除的节点的右孩子直接替代上要删除的节点，直接完成删除操作node = node.right;}}return node;}
}

解题思路：这道题主要是要找到要删除的位置，然后要考虑用谁来替代能不破坏BST的特性

找到要删除的位置就比较简单了，因为BST的特定，直接不断的判断就能找到；然后就是找到之后要如何进行替换，这里使用的方式是先找到要删除的节点的右子树中的最左子节点（这个节点肯定是没左孩子的），然后要删除的节点的左子树直接剪下来接到这个最左子节点的左孩子位置，然后现在相当于我们在右子树构建好了这些节点的相对位置，所以直接把要删除节点的右孩子替代掉它就行了

669. 修剪二叉搜索树

669. 修剪二叉搜索树 - 力扣（LeetCode）

class Solution {public TreeNode trimBST(TreeNode root, int low, int high) {return dfs(root, low, high);}private TreeNode dfs(TreeNode root, int low, int high) {if (root == null) return null;// 从这个节点开始的左子树都要删除，也就是直接把右子树拼接上就行// 其实这里就是剪枝的思想，只要判断到当前节点的值是不符合的，我们就直接当作是没遍历过这个节点，直接跳到它的子节点去，// 因为只要是遍历过的节点都是会拼接上的，因为我们最后面是直接把遍历到的节点返回出去if (root.val < low) return dfs(root.right, low, high);if (root.val > high) return dfs(root.left, low, high);// 递归处理左右子树root.left = dfs(root.left, low, high);root.right = dfs(root.right, low, high);// 将当前节点返回出去return root;}
}

解题思路：这道题其实就是直接使用递归，然后只要是遍历到的节点就直接返回出去，那么在这种情况下如何将不符合的节点去掉呢？既然遍历到的节点就会返回出去，那我加上一个剪枝逻辑，提前return掉，并且当作没遍历过这个节点，直接跳到它的子节点上不就行了

112. 路径总和

112. 路径总和 - 力扣（LeetCode）

class Solution {public boolean hasPathSum(TreeNode root, int targetSum) {if (root == null) return false;if (root.left == null && root.right == null) return root.val == targetSum;// 需要继续递归return hasPathSum(root.left, targetSum - root.val) || hasPathSum(root.right, targetSum - root.val);}
}

解题思路：这道题就是通过递归，然后不断的去尝试每一个节点，直接看代码就行了，就3行代码的事

这里因为是只要找到一条就行，所以用 ||

437. 路径总和 III

437. 路径总和 III - 力扣（LeetCode）

class Solution {private int ans = 0;public int pathSum(TreeNode root, int targetSum) {Map<Long, Integer> map = new HashMap<>();map.put(0L, 1);dfs(root, targetSum, 0, map);return ans;}/**** @param node* @param targetSum* @param cur 从根节点到当前节点的总路径之和* @param map*/private void dfs(TreeNode node, int targetSum, long cur, Map<Long, Integer> map) {if (node == null) return;// 假设现在这个点就是终点，那么有多少种情况是符合的cur += node.val;// cur - targetSum 是因为cur是从根节点到当前节点的总路径之和，// 那么只要map中有cur - targetSum就说明存在节点到这个节点符合条件ans += map.getOrDefault(cur - targetSum, 0);// 塞入一个新的路径进去map.put(cur, map.getOrDefault(cur, 0) + 1);// 进入下一层继续计算dfs(node.left, targetSum, cur, map);dfs(node.right, targetSum, cur, map);// 最后就是回滚一下前缀和map，避免影响到其他的分支的判断map.put(cur, map.getOrDefault(cur, 0) - 1);}
}

解题思路：这道题就是直接使用前缀和进行求解。

cur 是从根节点开始一直加到当前节点的路径之和，所以这里使用cur - targetSum 是因为cur是从根节点到当前节点的总路径之和，那么只要map中有cur - targetSum就说明存在节点到这个节点符合条件

最后就是注意要回滚一下前缀和的次数，因为假如进入到其他分支的话，不回滚会影响到其他分支的判断

230. 二叉搜索树中第K小的元素

230. 二叉搜索树中第 K 小的元素 - 力扣（LeetCode）

class Solution {private int res;private int count;public int kthSmallest(TreeNode root, int k) {dfs(root, k);return res;}private void dfs(TreeNode root, int k) {if (root == null) return;// 中序遍历dfs(root.left, k);count++;if (count == k) {res = root.val;return;}dfs(root.right, k);}
}

解题思路：直接通过中序遍历的方式，因为遍历出来的结果是递增的，那么我们再维护一个计数器，只要当计数器等于k就说明找到了

114. 二叉树展开为链表

114. 二叉树展开为链表 - 力扣（LeetCode）

class Solution {public void flatten(TreeNode root) {ArrayList<TreeNode> arrayList = new ArrayList<>();dfs(root, arrayList);for (int i = 0; i < arrayList.size() - 1; i++) {TreeNode prev = arrayList.get(i);TreeNode cur = arrayList.get(i + 1);prev.left = null;prev.right = cur;}}private void dfs(TreeNode node, List<TreeNode> list) {if (node == null) return;list.add(node);dfs(node.left, list);dfs(node.right, list);}
}class Solution {private TreeNode cur;public void flatten(TreeNode root) {dfs(root);root = cur;}private void dfs(TreeNode node) {if (node == null) return;dfs(node.right);dfs(node.left);node.left = null;node.right = cur;cur = node;}
}

解题思路：首先就是可以使用一个额外的集合来进行存储每次遍历到的节点（前序遍历，这一点可以通过题目看出来），然后再遍历一遍集合进行处理

还有一种不用借助到集合这种额外空间的方法，就是直接使用后序遍历（而且要右中左的顺序，这一点也是看看题目就能知道的），这种方法的话就是有点像是使用头插入来进行处理，所以还要维护一个额外的变量指向上一个处理的节点

Q：为什么这里要使用后序遍历？那前序是不是也可以？

A：前序可以，但是因为遍历到每一个节点的时候需要额外的去处理左右子树，会麻烦一点。

222. 完全二叉树的节点个数

222. 完全二叉树的节点个数 - 力扣（LeetCode）

class Solution {public int countNodes(TreeNode root) {if (root == null) return 0;return countNodes(root.left) + countNodes(root.right) + 1;}
}

解题思路：直接递归，每次不断累加就行了，这个加1可以理解为就是加上当前这个节点。

208. 实现 Trie (前缀树)

208. 实现 Trie (前缀树) - 力扣（LeetCode）

class Trie {class TreeNode {private TreeNode[] children = new TreeNode[26];private boolean isEnd = false;}TreeNode head = null;public Trie() {head = new TreeNode();}public void insert(String word) {TreeNode cur = head;for (char c : word.toCharArray()) {int index = c - 'a';if (cur.children[index] == null) {cur.children[index] = new TreeNode();}cur = cur.children[index];}cur.isEnd = true;}public boolean search(String word) {return find(word) == 1;}public boolean startsWith(String prefix) {return find(prefix) != 2;}private int find(String str) {// 判断是部分包含还是全部包含// 如果是部分的话就返回0 全部就返回1，返回2表示根本不存在TreeNode cur = head;for (char c : str.toCharArray()) {int index = c - 'a';if (cur.children[index] == null) return 2;cur = cur.children[index];}return cur.isEnd ? 1 : 0;}
}

解题思路：这道题其实可以看做是26叉树，因为一共是26个字母，所以每一个节点都可能有26个子节点，直接用一个数组来存储它的子节点，然后用一个标志来表示当前节点是否已经结束，从而表示是否为单词

具体的代码比较简单，直接看就行了