Day29——二叉树专题 Myth丶恋晨 2024-04-01 15:11 67阅读 0赞 #### 文章目录 #### * * * * 19.最大二叉树 * 20.合并二叉树 * 21.二叉搜索树中的搜索 -------------------- ##### 19.最大二叉树 ##### [力扣题目地址][Link 1] **思路** 给定一个不含重复元素的整数数组。一个以此数组构建的最大二叉树定义如下: * 二叉树的根是数组中的最大元素。 * 左子树是通过数组中最大值左边部分构造出的最大二叉树。 * 右子树是通过数组中最大值右边部分构造出的最大二叉树。 **递归三部曲** * 确定递归函数的参数和返回值 参数就是传入的是存放元素的数组,返回该数组构造的二叉树的头结点,返回类型是指向节点的指针。 * 确定终止条件 题目中说了输入的数组大小一定是大于等于1的,所以我们不用考虑小于1的情况,那么当递归遍历的时候,如果传入的数组大小为1,说明遍历到了叶子节点了。 那么应该定义一个新的节点,并把这个数组的数值赋给新的节点,然后返回这个节点。 这表示一个数组大小是1的时候,构造了一个新的节点,并返回。 * 确定单层递归的逻辑 1. 先要找到数组中最大的值和对应的下标, 最大的值构造根节点,下标用来下一步分割数组。 2. 最大值所在的下标左区间 构造左子树,这里要判断`maxValueIndex > 0`,因为要保证左区间至少有一个数值。 3. 最大值所在的下标右区间 构造右子树,判断`maxValueIndex < (nums.size() - 1)`,确保右区间至少有一个数值。 class Solution { public TreeNode constructMaximumBinaryTree(int[] nums) { return dfs(nums, 0, nums.length); } public TreeNode dfs(int[] nums, int leftIndex, int rightIndex) { if (rightIndex - leftIndex < 1) { // 没有元素了 return null; } if (rightIndex - leftIndex == 1) { // 只有一个元素 return new TreeNode(nums[leftIndex]); } int maxIndex = leftIndex;// 最大值所在位置 int maxVal = nums[maxIndex];// 最大值 for (int i = leftIndex + 1; i < rightIndex; i++) { if (nums[i] > maxVal){ maxVal = nums[i]; maxIndex = i; } } TreeNode root = new TreeNode(maxVal); // 根据maxIndex划分左右子树 root.left = dfs(nums, leftIndex, maxIndex); root.right = dfs(nums, maxIndex + 1, rightIndex); return root; } } ##### 20.合并二叉树 ##### [力扣题目链接][Link 2] **递归三部曲** **1.确定递归函数的参数和返回值:** 首先那么要合入两个二叉树,那么参数至少是要传入两个二叉树的根节点,返回值就是合并之后二叉树的根节点。 **2.确定终止条件:** 因为是传入了两个树,那么就有两个树遍历的节点t1 和 t2,如果t1 == NULL 了,两个树合并就应该是 t2 了啊(如果t2也为NULL也无所谓,合并之后就是NULL)。 反过来如果t2 == NULL,那么两个数合并就是t1(如果t1也为NULL也无所谓,合并之后就是NULL)。 **3.确定单层递归的逻辑:** 因为是传入了两个树,那么就有两个树遍历的节点t1 和 t2,如果t1 == NULL 了,两个树合并就应该是 t2 了啊(如果t2也为NULL也无所谓,合并之后就是NULL)。 反过来如果t2 == NULL,那么两个数合并就是t1(如果t1也为NULL也无所谓,合并之后就是NULL)。 **代码实现:dfs方式** 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; } } ##### 21.二叉搜索树中的搜索 ##### [力扣题目地址][Link 3] 二叉搜索树是一个有序树: * 若它的左子树不空,则左子树上所有结点的值均小于它的根结点的值; * 若它的右子树不空,则右子树上所有结点的值均大于它的根结点的值; * 它的左、右子树也分别为二叉搜索树 **代码实现** `DFS` class Solution { public TreeNode searchBST(TreeNode root, int val) { if(root==null||root.val==val) return root; TreeNode res = null; if(val>root.val) res = searchBST(root.right,val); if(val<root.val) res = searchBST(root.left,val); return res; } } **迭代法** class Solution { public TreeNode searchBST(TreeNode root, int val) { while(root!=null){ if(val>root.val) root=root.right; else if(val<root.val) root=root.left; else return root; } return null; } } [Link 1]: https://leetcode.cn/problems/maximum-binary-tree/ [Link 2]: https://leetcode.cn/problems/merge-two-binary-trees/ [Link 3]: https://leetcode.cn/problems/search-in-a-binary-search-tree/
相关 Day30——二叉树专题 文章目录 22.验证二叉搜索树 23.二叉搜索树的最小绝对差 24.二叉搜索树中的插入 谁借莪1个温暖的怀抱¢/ 2024年04月01日 15:23/ 0 赞/ 62 阅读
还没有评论,来说两句吧...