代码随想录算法训练营第十七天

目录

LeetCode.654 最大二叉树

题目链接 最大二叉树

题解

解题思路

LeetCode.617 合并二叉树

题目链接  合并二叉树

题解

解题思路

LeetCode.700 二叉搜索树中的搜索

题目链接 二叉搜索树中的搜索

题解

解题思路

解题思路

LeetCode.98 验证二叉搜索树

题目链接 验证二叉搜索树

题解

解题思路

解题思路

总结与收获

---

LeetCode.654 最大二叉树

题目链接 最大二叉树

题解

class Solution {public TreeNode constructMaximumBinaryTree(int[] nums) {return getRoot(nums,0,nums.length);}public TreeNode getRoot(int[] nums,int begin,int end){// 获得最大值int max_value = nums[begin];int index = begin;for(int i = index;i < end;i ++){if(max_value < nums[i]){index = i;max_value = nums[i];}}TreeNode root = new TreeNode(max_value);if(index > begin){root.left = getRoot(nums,begin,index);}if(index < end - 1){root.right = getRoot(nums,index + 1,end);}return root;}
}

解题思路

这段代码实现了构造最大二叉树（Maximum Binary Tree）的功能，核心思路是递归分治：每次从当前数组片段中找到最大值作为根节点，再递归处理左右子数组构建左右子树。具体步骤如下：

1. 主函数入口：constructMaximumBinaryTree 初始化递归，传入整个数组范围 [0, nums.length)。

2. 递归构建树：辅助函数 getRoot 负责：

   • 寻找最大值：遍历当前范围 [begin, end)，找到最大值及其索引。
   • 创建根节点：用最大值创建当前子树的根。
   • 递归处理左右子树：
     • 左子树：处理范围 [begin, index)（即最大值左侧元素）。
     • 右子树：处理范围 [index+1, end)（即最大值右侧元素）。
   • 返回当前根节点：将左右子树连接到根节点后返回。

3. 递归终止条件：当 begin >= end 时（即处理空数组片段），返回 null。

LeetCode.617 合并二叉树

题目链接  合并二叉树

题解

class Solution {public TreeNode mergeTrees(TreeNode root1, TreeNode root2) {if(root1 == null) return root2;if(root2 == null) return root1;root1.val += root2.val;root1.left = mergeTrees(root1.left,root2.left);root1.right = mergeTrees(root1.right,root2.right);return root1;}
}

解题思路

使用前序遍历，同时对两个树进行遍历。

LeetCode.700 二叉搜索树中的搜索

题目链接 二叉搜索树中的搜索

题解

class Solution {public TreeNode searchBST(TreeNode root, int val) {if(root == null) return null;if(root.val == val) return root;TreeNode resNode = null;if(val < root.val) resNode = searchBST(root.left,val);if(val > root.val) resNode = searchBST(root.right,val);return resNode;}
}

解题思路

这段代码实现了在  二叉搜索树（BST） 中查找值为 val 的节点。解题思路基于 BST 的特性：左子树所有节点值小于根节点，右子树所有节点值大于根节点，因此可以通过比较当前节点值与目标值的大小，递归地缩小搜索范围。

解题思路

1. BST 特性利用

   • 若当前节点值等于 val，直接返回当前节点。
   • 若 val 小于当前节点值，只需在左子树中继续搜索（因为右子树所有值都更大）。
   • 若 val 大于当前节点值，只需在右子树中继续搜索（因为左子树所有值都更小）。

2. 递归搜索过程

   • 终止条件：当前节点为空（未找到）或当前节点值等于 val（找到目标）。
   • 递归逻辑：根据当前节点值与 val 的大小关系，选择左子树或右子树继续搜索，并返回搜索结果。

3. 代码实现步骤

   • 检查当前节点：若为空或值匹配，直接返回。
   • 递归搜索：
     • 若 val < root.val，递归搜索左子树。
     • 若 val > root.val，递归搜索右子树。
   • 返回结果：递归调用的结果即为最终结果。

LeetCode.98 验证二叉搜索树

题目链接 验证二叉搜索树

题解

class Solution {private long prev = Long.MIN_VALUE;public boolean isValidBST(TreeNode root) {if(root == null) return true;if(!isValidBST(root.left)) return false;if(root.val <= prev) return false;prev = root.val;return isValidBST(root.right);}
}

解题思路

这段代码通过中序遍历（In-order Traversal）的方式验证二叉树是否为合法的二叉搜索树（BST）。解题的核心思路是利用 BST 的中序遍历结果为严格升序序列这一特性，通过递归遍历过程中检查每个节点的值是否严格大于前一个访问的节点值。

解题思路

1. BST 的中序遍历特性

   • 对于合法的 BST，中序遍历（左 → 根 → 右）的输出必须是严格递增的序列。
   • 例如，BST [2,1,3] 的中序遍历为 [1,2,3]，严格递增。

2. 递归中序遍历验证

   • 使用全局变量 prev 记录中序遍历过程中前一个节点的值（初始化为 Long.MIN_VALUE）。
   • 递归遍历左子树，若左子树不合法则直接返回 false。
   • 检查当前节点值是否大于 prev，若不大于则返回 false。
   • 更新 prev 为当前节点值，递归遍历右子树。

3. 代码实现步骤

   • 终止条件：空树视为合法 BST，返回 true。
   • 递归左子树：验证左子树是否合法。
   • 检查当前节点：确保当前节点值大于 prev，并更新 prev。
   • 递归右子树：验证右子树是否合法。

总结与收获

总结上述二叉树相关题目解法，核心均围绕递归与树的特性展开。构造最大二叉树用递归分治，以最大值为根划分左右子树；合并二叉树通过前序遍历同步处理两树节点；BST 搜索和验证则依托其左小右大特性，分别用递归缩小范围和中序遍历检查升序。这些解法体现了递归在树问题中的高效应用，以及利用数据结构特性简化逻辑的关键思路。