代码随想录二叉树第四周

617.合并二叉树

700.二叉搜索树中的搜索

98.验证二叉搜索树

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

501.二叉搜索树中的众树

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

617.合并二叉树

617. 合并二叉树

简单

给你两棵二叉树： root1 和 root2 。

想象一下，当你将其中一棵覆盖到另一棵之上时，两棵树上的一些节点将会重叠（而另一些不会）。你需要将这两棵树合并成一棵新二叉树。合并的规则是：如果两个节点重叠，那么将这两个节点的值相加作为合并后节点的新值；否则，不为 null 的节点将直接作为新二叉树的节点。

返回合并后的二叉树。

注意: 合并过程必须从两个树的根节点开始。

示例 1：

输入：root1 = [1,3,2,5], root2 = [2,1,3,null,4,null,7]
输出：[3,4,5,5,4,null,7]

示例 2：

输入：root1 = [1], root2 = [1,2]
输出：[2,2]

提示：

两棵树中的节点数目在范围 [0, 2000] 内
-104 <= Node.val <= 104

递归法：

/*** Definition for a binary tree node.* public class TreeNode {*     int val; // 节点值*     TreeNode left; // 左子节点*     TreeNode right; // 右子节点*     TreeNode() {} // 无参构造函数*     TreeNode(int val) { this.val = val; } // 带值构造函数*     TreeNode(int val, TreeNode left, TreeNode right) { // 带值和子节点的构造函数*         this.val = val;*         this.left = left;*         this.right = right;*     }* }*/// 解题思路：
// 使用递归，对两棵树的对应节点进行合并，如果其中一个节点为空，则返回另一个节点，否则，将两个节点的值相加作为新节点的值，
// 然后递归合并它们的左右子树。class Solution {public TreeNode mergeTrees(TreeNode root1, TreeNode root2) {// 如果两个根节点都为空，则返回空if (root1 == null && root2 == null) {return null;}// 如果其中一个根节点为空，则返回另一个根节点if (root1 == null && root2 != null) {return root2;}if (root2 == null && root1 != null) {return root1;}// 创建一个新的节点，值为两个根节点值的和TreeNode node = new TreeNode();node.val = root1.val + root2.val;// 递归合并左子树和右子树node.left = mergeTrees(root1.left, root2.left);node.right = mergeTrees(root1.right, root2.right);return node; // 返回合并后的根节点}
}

迭代法：

/*** Definition for a binary tree node.* public class TreeNode {*     int val;*     TreeNode left;*     TreeNode right;*     TreeNode() {}*     TreeNode(int val) { this.val = val; }*     TreeNode(int val, TreeNode left, TreeNode right) {*         this.val = val;*         this.left = left;*         this.right = right;*     }* }*/
class Solution {public TreeNode mergeTrees(TreeNode root1, TreeNode root2) {// 如果第一棵树为空，则返回第二棵树if(root1 == null){return root2;}// 如果第二棵树为空，则返回第一棵树if(root2 == null){return root1;}// 创建一个队列，用于按层遍历二叉树Queue<TreeNode> queue = new LinkedList<>();// 将第一棵树的根节点和第二棵树的根节点加入队列queue.offer(root1);queue.offer(root2);// 循环处理队列中的节点while(!queue.isEmpty()){// 依次从队列中取出两棵树的节点TreeNode node1 = queue.poll();TreeNode node2 = queue.poll();// 合并两棵树的当前节点的值node1.val += node2.val;// 如果两棵树的左子节点均不为空，则将左子节点加入队列if(node1.left != null && node2.left != null){queue.offer(node1.left);queue.offer(node2.left);}// 如果第一棵树的左子节点为空而第二棵树的左子节点不为空，则将第二棵树的左子节点赋给第一棵树if(node1.left == null && node2.left != null){node1.left = node2.left;}// 如果两棵树的右子节点均不为空，则将右子节点加入队列if(node1.right != null && node2.right != null){queue.offer(node1.right);queue.offer(node2.right);}// 如果第一棵树的右子节点为空而第二棵树的右子节点不为空，则将第二棵树的右子节点赋给第一棵树if(node1.right == null && node2.right != null){node1.right = node2.right;}}// 返回第一棵树return root1;}
}

700.二叉搜索树中的搜索

700. 二叉搜索树中的搜索

简单

给定二叉搜索树（BST）的根节点 root 和一个整数值 val。

你需要在 BST 中找到节点值等于 val 的节点。返回以该节点为根的子树。如果节点不存在，则返回 null 。

示例 1:

输入：root = [4,2,7,1,3], val = 2
输出：[2,1,3]

示例 2:

输入：root = [4,2,7,1,3], val = 5
输出：[]

提示：

树中节点数在 [1, 5000] 范围内
1 <= Node.val <= 107
root 是二叉搜索树
1 <= val <= 107

递归法：

/*** Definition for a binary tree node.* public class TreeNode {*     int val;*     TreeNode left;*     TreeNode right;*     TreeNode() {}*     TreeNode(int val) { this.val = val; }*     TreeNode(int val, TreeNode left, TreeNode right) {*         this.val = val;*         this.left = left;*         this.right = right;*     }* }*/
class Solution {public TreeNode searchBST(TreeNode root, int val) {// 如果根节点为空或者根节点的值等于目标值，则返回根节点if(root == null || root.val == val){return root;}// 定义一个用于存储搜索结果的节点TreeNode node = new TreeNode();// 如果根节点的值小于目标值，则在右子树中搜索if(root.val < val){node = searchBST(root.right,val);}// 如果根节点的值大于目标值，则在左子树中搜索if(root.val > val){node = searchBST(root.left,val);}// 返回搜索到的节点return node;}
}

迭代法：

/*** Definition for a binary tree node.* public class TreeNode {*     int val;*     TreeNode left;*     TreeNode right;*     TreeNode() {}*     TreeNode(int val) { this.val = val; }*     TreeNode(int val, TreeNode left, TreeNode right) {*         this.val = val;*         this.left = left;*         this.right = right;*     }* }*/
class Solution {public TreeNode searchBST(TreeNode root, int val) {// 当根节点不为null时，执行循环while(root != null){// 如果根节点的值大于目标值，则继续在左子树中搜索if(root.val > val){root = root.left;}// 如果根节点的值小于目标值，则继续在右子树中搜索else if(root.val < val){root = root.right;}// 如果根节点的值等于目标值，则返回根节点else{return root;}}// 如果根节点为null，则表示未找到目标值，返回nullreturn root;}
}

98.验证二叉搜索树

98. 验证二叉搜索树

中等

给你一个二叉树的根节点 root ，判断其是否是一个有效的二叉搜索树。

有效二叉搜索树定义如下：

节点的左子树只包含小于当前节点的数。
节点的右子树只包含大于当前节点的数。
所有左子树和右子树自身必须也是二叉搜索树。

示例 1：

输入：root = [2,1,3]
输出：true

示例 2：

输入：root = [5,1,4,null,null,3,6]
输出：false
解释：根节点的值是 5 ，但是右子节点的值是 4 。

提示：

树中节点数目范围在[1, 104] 内
-231 <= Node.val <= 231 - 1

经过中序遍历的话，二叉搜索树遍历的顺序，val值是从小到大的，设定一个pre节点，判断在中序遍历时，每个节点是否都比前一个节点要大，如果满足条件即为二叉搜索树

这里会有一个经常忽略的地方就是只判断左节点<中节点<右节点,这样就无法判断下图情况

重点在于要明白二叉搜索树的定义

递归法：（这里的递归法思路更清晰）

/*** Definition for a binary tree node.* public class TreeNode {*     int val;*     TreeNode left;*     TreeNode right;*     TreeNode() {}*     TreeNode(int val) { this.val = val; }*     TreeNode(int val, TreeNode left, TreeNode right) {*         this.val = val;*         this.left = left;*         this.right = right;*     }* }*/
class Solution {// 用于保存前一个节点的引用TreeNode pre = null;/*** 判断给定的二叉树是否为有效的二叉搜索树* @param root 给定二叉树的根节点* @return 如果是有效的二叉搜索树，则返回true；否则返回false*/public boolean isValidBST(TreeNode root) {// 如果根节点为空，则是有效的二叉搜索树if(root == null){return true;}// 递归判断左子树是否为有效的二叉搜索树boolean leftBoolean = isValidBST(root.left);// 如果前一个节点不为空且前一个节点的值大于等于当前节点的值，则不是有效的二叉搜索树if(pre != null && pre.val >= root.val){return false;}// 更新前一个节点的引用为当前节点pre = root;// 递归判断右子树是否为有效的二叉搜索树boolean rightBoolean = isValidBST(root.right);// 返回左右子树判断结果的逻辑与return leftBoolean && rightBoolean;}
}

迭代法：

import java.util.Queue;
import java.util.LinkedList;class Solution {// 迭代方法验证二叉搜索树public boolean isValidBST(TreeNode root) {if (root == null) {return true; // 空树被视为有效的二叉搜索树}// 使用队列代替栈，模拟中序遍历过程Queue<TreeNode> queue = new LinkedList<>();TreeNode pre = null; // 用于保存前一个节点// 当根节点不为空或队列不为空时，循环执行while (root != null || !queue.isEmpty()) {// 将当前节点的左子树全部入队列while (root != null) {queue.add(root);root = root.left; // 移动到左子节点}// 处理当前节点TreeNode front = queue.remove(); // 出队列if (pre != null && front.val <= pre.val) {return false; // 如果当前节点的值小于等于前一个节点的值，返回 false}pre = front; // 更新前一个节点为当前节点root = front.right; // 处理右子树，移动到右子节点}return true; // 所有节点都遍历完成，返回 true，代表是二叉搜索树}
}

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

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

已解答

简单

501.二叉搜索树中的众树

501. 二叉搜索树中的众数

简单

给你一个含重复值的二叉搜索树（BST）的根节点 root ，找出并返回 BST 中的所有众数（即，出现频率最高的元素）。

如果树中有不止一个众数，可以按 任意顺序 返回。

假定 BST 满足如下定义：

结点左子树中所含节点的值 小于等于 当前节点的值
结点右子树中所含节点的值 大于等于 当前节点的值
左子树和右子树都是二叉搜索树

示例 1：

输入：root = [1,null,2,2]
输出：[2]

示例 2：

输入：root = [0]
输出：[0]

提示：

树中节点的数目在范围 [1, 104] 内
-105 <= Node.val <= 105

进阶：你可以不使用额外的空间吗？（假设由递归产生的隐式调用栈的开销不被计算在内）

暴力解法：使用map集合记录出现次数，排序后取出最大的

class Solution {public int[] findMode(TreeNode root) {// 创建一个映射表，用于存储节点值及其出现的频率Map<Integer, Integer> map = new HashMap<>();// 创建一个列表，用于存储出现频率最高的节点值List<Integer> list = new ArrayList<>();// 如果根节点为空，则返回空数组if (root == null) return new int[0];// 获取树中节点值的频率映射searchBST(root, map);// 将映射表中的条目按值的降序排序List<Map.Entry<Integer, Integer>> mapList = new ArrayList<>(map.entrySet());mapList.sort(new Comparator<Map.Entry<Integer, Integer>>() {@Overridepublic int compare(Map.Entry<Integer, Integer> c1, Map.Entry<Integer, Integer> c2) {return c2.getValue().compareTo(c1.getValue());}});// 将出现频率最高的节点值添加到列表中list.add(mapList.get(0).getKey());// 将与最高频率相同的节点值也添加到列表中for (int i = 1; i < mapList.size(); i++) {if (mapList.get(i).getValue().equals(mapList.get(i - 1).getValue())) {list.add(mapList.get(i).getKey());} else {break;}}// 将列表转换为数组并返回int[] result = new int[list.size()];for (int i = 0; i < list.size(); i++) {result[i] = list.get(i);}return result;}// 辅助方法：遍历二叉搜索树并更新频率映射void searchBST(TreeNode curr, Map<Integer, Integer> map) {if (curr == null) return;// 更新节点值的频率map.put(curr.val, map.getOrDefault(curr.val, 0) + 1);// 递归遍历左子树和右子树searchBST(curr.left, map);searchBST(curr.right, map);}}

使用pre指针和当前指针比较，动态更新count，记录maxCount，更新list中的元素

class Solution {TreeNode pre = null;    // 前一个节点int count = 0;          // 当前节点值的出现次数int maxCount = 0;       // 最大出现次数List<Integer> list = new ArrayList<>(); // 结果列表/*** 查找众数* @param root 二叉树的根节点* @return 众数数组*/public int[] findMode(TreeNode root) {getMode(root);      // 调用获取众数的方法int[] result = new int[list.size()];    // 初始化结果数组for(int i = 0; i < list.size(); i++){   // 将结果列表转换为数组result[i] = list.get(i);}return result;      // 返回结果数组}/*** 获取众数* @param root 当前节点*/public void getMode(TreeNode root){if(root == null){   // 如果当前节点为空，直接返回return;}getMode(root.left);     // 递归处理左子树// 如果前一个节点为空，表示当前节点是第一个节点，出现次数初始化为1// 否则，如果当前节点值和前一个节点值相同，出现次数加1，否则重置为1if(pre == null){count = 1;} else if(pre.val == root.val){count ++;} else {count = 1;}// 如果当前节点出现次数等于最大出现次数，则加入结果列表// 如果当前节点出现次数大于最大出现次数，更新最大出现次数和结果列表if(count == maxCount){list.add(root.val);} else if(count > maxCount){maxCount = count;list.clear();list.add(root.val);}pre = root;     // 更新前一个节点getMode(root.right);    // 递归处理右子树}
}