首页 > 编程语言 >代码随想录算法训练Day20|LeetCode654-最大二叉树、LeetCode617-合并二叉树、LeetCode707-二叉搜索树中的搜索、LeetCode98-验证二叉搜索树

代码随想录算法训练Day20|LeetCode654-最大二叉树、LeetCode617-合并二叉树、LeetCode707-二叉搜索树中的搜索、LeetCode98-验证二叉搜索树

时间：2024-05-28 19:31:44浏览次数：35  
标签：return val 二叉 搜索 二叉树 TreeNode null root left

最大二叉树

题目描述

力扣654-最大二叉树

给定一个不重复的整数数组 nums 。 最大二叉树 可以用下面的算法从 nums 递归地构建:

  1. 创建一个根节点，其值为 nums 中的最大值。
  2. 递归地在最大值 左边 的 子数组前缀上 构建左子树。
  3. 递归地在最大值 右边 的 子数组后缀上 构建右子树。

返回 nums 构建的 最大二叉树 。

654.最大二叉树

构造树一般采用的是前序遍历，因为先构造中间节点，然后递归构造左子树和右子树。

示例 1：

在这里插入图片描述

输入：nums = [3,2,1,6,0,5]
输出：[6,3,5,null,2,0,null,null,1]
解释：递归调用如下所示：
- [3,2,1,6,0,5] 中的最大值是 6 ，左边部分是 [3,2,1] ，右边部分是 [0,5] 。
    - [3,2,1] 中的最大值是 3 ，左边部分是 [] ，右边部分是 [2,1] 。
        - 空数组，无子节点。
        - [2,1] 中的最大值是 2 ，左边部分是 [] ，右边部分是 [1] 。
            - 空数组，无子节点。
            - 只有一个元素，所以子节点是一个值为 1 的节点。
    - [0,5] 中的最大值是 5 ，左边部分是 [0] ，右边部分是 [] 。
        - 只有一个元素，所以子节点是一个值为 0 的节点。
        - 空数组，无子节点。

示例 2：

在这里插入图片描述

输入：nums = [3,2,1]
输出：[3,null,2,null,1]

提示：

  • 1 <= nums.length <= 1000
  • 0 <= nums[i] <= 1000
  • nums 中的所有整数 互不相同

解题思路

构造树一般采用的是前序遍历，因为先构造中间节点，然后递归构造左子树和右子树。

1.确定递归函数的参数和返回值

参数传入的是存放元素的数组以及数组的上下标，返回该数组构造的二叉树的头结点，返回类型是按此数组构造的最大二叉树的根节点

public TreeNode constructMaximumBinaryTree1(int[] nums, int leftIndex, int rightIndex)

2.确定终止条件

  if (left >= right)//1.终止条件 如果 left >= right，则返回 null，表示当前区间无元素。
            return null;

3.确定单层递归的逻辑

按左闭右开

首先找到该数组中的最大值对应的坐标maxValueIndex，按此分割左右子数组[left, maxValueIndex)、[maxValueIndex + 1, right)

构建左最大二叉树与右最大二叉树

        // 分割点下标：maxValueIndex,循环遍历找到最大值的下标
        int maxValueIndex = left;
        for (int i = left + 1; i < right; ++i) {
            if (nums[i] > nums[maxValueIndex])
                maxValueIndex = i;
        }
      
        //创建一个新节点 TreeNode，值为最大值 nums[maxValueIndex]。
        TreeNode root = new TreeNode(nums[maxValueIndex]);

        // 左闭右开--->左子树:区间：[left, maxValueIndex)
        root.left = traversal(nums, left, maxValueIndex);

        // 左闭右开--->右子树:区间：[maxValueIndex + 1, right)
        root.right = traversal(nums, maxValueIndex + 1, right);

        return root;

在整个递归过程中数组nums是不变的，不去每次构造新数组，而是直接操作下标

参考解题

优化：不去每次构造新数组，而是直接操作下标

class Solution {
    public TreeNode constructMaximumBinaryTree(int[] nums) {
        return constructMaximumBinaryTree1(nums, 0, nums.length);
    }

    public TreeNode constructMaximumBinaryTree1(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 = constructMaximumBinaryTree1(nums, leftIndex, maxIndex);
        root.right = constructMaximumBinaryTree1(nums, maxIndex + 1, rightIndex);
        return root;
    }
}

补充

凡是构造二叉树的题目都要用前序遍历（中、左、右）

合并二叉树

题目描述

力扣617-合并二叉树
给你两棵二叉树： root1 和 root2 。

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

返回合并后的二叉树。

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

示例 1：

img

输入：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

解题思路

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

和遍历一个树逻辑是一样的，只不过传入两个树的节点，同时操作

二叉树使用递归，就要想使用前中后哪种遍历方式？

本题使用哪种遍历都是可以

我们下面以前序遍历为例。

动画如下：

617.合并二叉树

递归三部曲

1.确定递归函数的参数和返回值

首先要合入两个二叉树，那么参数至少是要传入两个二叉树的根节点，返回值就是合并之后二叉树的根节点。

代码如下：

public TreeNode mergeTrees(TreeNode root1, TreeNode root2)

2.确定终止条件

因为是传入了两个树，那么就有两个树遍历的节点root1 和 root2，如果root1 == NULL 了，两个树合并就应该是 root2了（如果root2也为NULL也无所谓，合并之后就是NULL）。

反过来如果root2 == NULL，那么两个数合并就是root1（如果root1也为NULL也无所谓，合并之后就是NULL）。

代码如下：

if (root1 == null) return root2;// 如果root1为空，合并之后就应该是root2为空，合并之后就应该是root2
if (root2 == null) return root1;

3.确定单层递归逻辑

那么单层递归中，就要把两棵树的元素加到一起。

root1.val += root2.val;

接下来root1 的左子树是：合并 root1左子树 root2左子树之后的左子树。

root1 的右子树：是 合并 root1右子树 root2右子树之后的右子树。

最终root1就是合并之后的根节点。

  root1.left = mergeTrees(root1.left,root2.left);
        root1.right = mergeTrees(root1.right,root2.right);
        return root1;

前序遍历---->递归整体代码如下：

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;
    }
}

如上的方法修改了t1的结构，当然也可以不修改t1和t2的结构，重新定义一个树。

class Solution {
    public TreeNode mergeTrees(TreeNode root1, TreeNode root2) {
        if (root1 == null) return root2;
        if (root2 == null) return root1;
        // 重新定义新的节点，不修改原有两个树的结构
        TreeNode root = new TreeNode(root1.val + root2.val);
        root.left = mergeTrees(root1.left, root2.left);
        root.right = mergeTrees(root1.right, root2.right);
        return root;
    }
}

二叉搜索树中的搜索

题目描述

力扣707-二叉搜索树中的搜索

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

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

示例 1:

img

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

示例 2:

img

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

提示：

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

解题思路

二叉搜索树是一个有序树：

  • 若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值；
  • 若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值；
  • 它的左、右子树也分别为二叉搜索树

这就决定了，二叉搜索树，递归遍历和迭代遍历和普通二叉树都不一样。

递归法

1.确定递归函数的参数和返回值

递归函数的参数传入的就是根节点和要搜索的数值，返回的就是以这个搜索数值所在的节点。

代码如下：

public TreeNode searchBST(TreeNode root, int val)

2.确定终止条件

如果root为空，或者找到这个数值了，就返回root节点。

  // 下面这两种情况可以合并在一起，直接返回root即可
        // if(root==null)return null;
        // if(root.val==val)return root;

        if (root == null || root.val == val)
            return root;

3.确定单层递归的逻辑

看看二叉搜索树的单层递归逻辑有何不同。

因为二叉搜索树的节点是有序的，所以可以有方向的去搜索。

如果root->val > val，搜索左子树，如果root->val < val，就搜索右子树，最后如果都没有搜索到，就返回NULL。

自己解题

/**
 * 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) {

        // 下面这两种情况可以合并在一起，直接返回root即可
        // if(root==null)return null;
        // if(root.val==val)return root;

        if (root == null || root.val == val)
            return root;
        // 非空且根节点值与目标值不相等，进行下面的判断：
        if (root.val > val)// 根节点大于目标值，搜索左子树
            return searchBST(root.left, val);
        else if (root.val < val)// 根节点小于目标值，搜索右子树
            return searchBST(root.right, val);

        // return root; //没有合并初始条件的时候是这么写的
        return null;// 均不满足

    }
}

迭代法（很简单）

二叉树遍历的迭代法，可能立刻想起使用栈来模拟深度遍历，使用队列来模拟广度遍历。

对于二叉搜索树可就不一样了，因为二叉搜索树的特殊性，也就是节点的有序性，可以不使用辅助栈或者队列就可以写出迭代法。

对于一般二叉树，递归过程中还有回溯的过程，例如走一个左方向的分支走到头了，那么要调头，在走右分支。

而对于二叉搜索树，不需要回溯的过程，因为节点的有序性就帮我们确定了搜索的方向。

class Solution {
    // 迭代，利用二叉搜索树特点，优化，可以不需要栈
    public TreeNode searchBST(TreeNode root, int val) {
        while (root != null)
            if (val < root.val)
                root = root.left;
            else if (val > root.val)
                root = root.right;
            else
                return root;
        return null;
    }
}

参考解题

class Solution {
    // 递归，普通二叉树
    public TreeNode searchBST(TreeNode root, int val) {
        if (root == null || root.val == val) {
            return root;
        }
        TreeNode left = searchBST(root.left, val);
        if (left != null) {
            return left;
        }
        return searchBST(root.right, val);
    }
}
-------------------------------------------------------------------------------------
class Solution {
    // 递归，利用二叉搜索树特点，优化
    public TreeNode searchBST(TreeNode root, int val) {
        if (root == null || root.val == val) {
            return root;
        }
        if (val < root.val) {
            return searchBST(root.left, val);
        } else {
            return searchBST(root.right, val);
        }
    }
}
-------------------------------------------------------------------------------------
class Solution {
    // 迭代，普通二叉树 用栈
    public TreeNode searchBST(TreeNode root, int val) {
        if (root == null || root.val == val) {
            return root;
        }
        Stack<TreeNode> stack = new Stack<>();
        stack.push(root);
        while (!stack.isEmpty()) {
            TreeNode pop = stack.pop();
            if (pop.val == val) {
                return pop;
            }
            if (pop.right != null) {
                stack.push(pop.right);
            }
            if (pop.left != null) {
                stack.push(pop.left);
            }
        }
        return null;
    }
}
-------------------------------------------------------------------------------------
class Solution {
    // 迭代，利用二叉搜索树特点，优化，可以不需要栈
    public TreeNode searchBST(TreeNode root, int val) {
        while (root != null)
            if (val < root.val)
                root = root.left;
            else if (val > root.val)
                root = root.right;
            else
                return root;
        return null;
    }
}

补充

递归法需要确定好递归的三部曲

验证二叉搜索树

题目描述

力扣98-验证二叉搜索树

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

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

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

示例 1：

img

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

示例 2：

img

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

提示：

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

解题思路

1.转化为数组

要知道中序遍历下，输出的二叉搜索树节点的数值是有序序列。

有了这个特性，验证二叉搜索树，就相当于变成了判断一个序列是不是递增的了。

中序遍历结果元素如果是单调递增的那么这棵树就是二叉搜索树

可以递归中序遍历将二叉搜索树转变成一个数组，代码如下：

private List<Integer> list = new ArrayList<>();

    private void traversal(TreeNode root) {
        if (root == null)
            return;
        traversal(root.left);
        list.add(root.val); // 将二叉搜索树转换为有序数组
        traversal(root.right);
    }

然后只要比较一下，这个数组是否是有序的，注意二叉搜索树中不能有重复元素。

traversal(root);
        for (int i = 1; i < list.size(); i++) {
            // 注意要小于等于，搜索树里不能有相同元素
            if (list.get(i) <= list.get(i - 1))
                return false;
        }
        return true;

转化为数组比较的整体代码

class Solution {
    public boolean isValidBST(TreeNode root) {
        list.clear(); // 清除列表以确保没有残留数据
        traversal(root);
        for (int i = 1; i < list.size(); i++) {
            // 注意要小于等于，搜索树里不能有相同元素
            if (list.get(i) <= list.get(i - 1))
                return false;
        }
        return true;
    }

    private List<Integer> list = new ArrayList<>();

    private void traversal(TreeNode root) {
        if (root == null)
            return;
        traversal(root.left);
        list.add(root.val); // 将二叉搜索树转换为有序数组
        traversal(root.right);
    }
}

以上代码中，我们把二叉树转变为数组来判断，是最直观的，但其实不用转变成数组，可以在递归遍历的过程中直接判断是否有序

2.递归

递归三部曲：

1.确定递归函数，返回值以及参数

要定义一个longlong的全局变量，用来比较遍历的节点是否有序，因为后台测试数据中有int最小值，所以定义为longlong的类型，初始化为longlong最小值。

注意递归函数要有bool类型的返回值， 我们在[二叉树：递归函数究竟什么时候需要返回值，什么时候不要返回值？]中讲了，只有寻找某一条边（或者一个节点）的时候，递归函数会有bool类型的返回值。

其实本题是同样的道理，我们在寻找一个不符合条件的节点，如果没有找到这个节点就遍历了整个树，如果找到不符合的节点了，立刻返回。

代码如下

public boolean isValidBST(TreeNode root)

2.确定终止条件

如果是空节点 是不是二叉搜索树呢？

是的，二叉搜索树也可以为空！

代码如下：

if (root == null) {
            return true;
        }
  • 确定单层递归的逻辑

中序遍历，一直更新max.val，一旦发现root.val <= maxVal，就返回false，注意元素相同时候也要返回false。

代码如下：

递归整体代码

class Solution {
    private long maxVal = Long.MIN_VALUE; // 因为后台测试数据中有int最小值

    public boolean isValidBST(TreeNode root) {
        if (root == null) {
            return true;
        }

        boolean left = isValidBST(root.left);//左
        // 中序遍历，验证遍历的元素是不是从小到大
        if (maxVal < root.val) {
            maxVal = root.val;
        } else {
            return false;
        }
        boolean right = isValidBST(root.right);//右

        return left && right;
    }
}

3.迭代

见参考解题

自己解题

class Solution {
    // 本身测试数据有比int数据要小，所以定义为long 类型
    long pre = Long.MIN_VALUE;

    public boolean isValidBST(TreeNode root) {
        // 从下往上递归，为null的时候都为true
        if (root == null)
            return true;

        // 左节点递归
        boolean left = isValidBST(root.left);

        // 根节点处理，如果是按照顺序，则记住pre是上一个节点，遍历到最后是顺序的，就是二叉搜索树
        // 使用pre来记住上一个节点
        if (root.val > pre)
            pre = root.val;
        // 如果不是，则提前返回false，不用再搜索右子树了
        else
            return false;

        boolean right = isValidBST(root.right);

        return left && right;
    }
}

参考解题

//使用統一迭代法
class Solution {
    public boolean isValidBST(TreeNode root) {
        Stack<TreeNode> stack = new Stack<>();
        TreeNode pre = null;
        if(root != null)
            stack.add(root);        
        while(!stack.isEmpty()){
            TreeNode curr = stack.peek();
            if(curr != null){
                stack.pop();
                if(curr.right != null)
                    stack.add(curr.right);
                stack.add(curr);
                stack.add(null);
                if(curr.left != null)
                    stack.add(curr.left);
            }else{
                stack.pop();
                TreeNode temp = stack.pop();
                if(pre != null && pre.val >= temp.val)
                    return false;
                pre = temp;
            }
        }
        return true;
    }
}

class Solution {
    // 递归
    TreeNode max;
    public boolean isValidBST(TreeNode root) {
        if (root == null) {
            return true;
        }
        // 左
        boolean left = isValidBST(root.left);
        if (!left) {
            return false;
        }
        // 中
        if (max != null && root.val <= max.val) {
            return false;
        }
        max = root;
        // 右
        boolean right = isValidBST(root.right);
        return right;
    }
}

class Solution {
    // 迭代
    public boolean isValidBST(TreeNode root) {
        if (root == null) {
            return true;
        }
        Stack<TreeNode> stack = new Stack<>();
        TreeNode pre = null;
        while (root != null || !stack.isEmpty()) {
            while (root != null) {
                stack.push(root);
                root = root.left;// 左
            }
            // 中，处理
            TreeNode pop = stack.pop();
            if (pre != null && pop.val <= pre.val) {
                return false;
            }
            pre = pop;

            root = pop.right;// 右
        }
        return true;
    }
}

// 简洁实现·递归解法
class Solution {
    public boolean isValidBST(TreeNode root) {
        return validBST(Long.MIN_VALUE, Long.MAX_VALUE, root);
    }
    boolean validBST(long lower, long upper, TreeNode root) {
        if (root == null) return true;
        if (root.val <= lower || root.val >= upper) return false;
        return validBST(lower, root.val, root.left) && validBST(root.val, upper, root.right);
    }
}
// 简洁实现·中序遍历
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);
    }
}

补充

做好相关复习
ps:部分图片和代码来自代码随想录和Leetcode官网

标签：return,val,二叉,搜索,二叉树,TreeNode,null,root,left
From： https://blog.csdn.net/m0_75002567/article/details/139275703

相关文章

  • 用正则表达式进行搜索
    检索列prod_name包含文本1000的所有行selectprod_namefromproductswhereprod_nameREGEXP'1000'orderbyprod_name;.在正则中表示一个字符selectprod_namefromproductswhereprod_nameREGEXP'.000'orderbyprod_name;结果：Jet1000Jet2000OR匹配sel......
  • 7款优秀的AI搜索引擎工具推荐
    AI搜索引擎不仅能够理解复杂的查询语句，还能够通过学习用户的搜索习惯和偏好，提供更加个性化的搜索结果。本篇文章将介绍7款在这一领域表现出色的AI搜索引擎工具，它们各有特色，但都致力于为用户提供更加智能、高效和精准的搜索体验。传统的搜索引擎在处理模糊或多义性强的查询时往往......
  • 二叉树——堆详解
    目录前言：一、堆的结构二、向上调整和向下调整    2.1向上调整    2.2向下调整    2.3向上调整和向下调整时间复杂度比较三、堆的实现    3.1堆的初始化    3.2堆的销毁    3.3堆的插入       ......
  • 基于C++的二叉树的创建与遍历（免费提供源码）
    下载地址如下：上传明细-CSDN创作中心项目介绍背景二叉树作为一种常见的数据结构，在计算机科学和编程实践中占有重要地位。它广泛应用于搜索算法、排序算法、表达式解析、符号表以及各种数据库索引结构中。因此，掌握二叉树的创建和遍历是计算机科学领域的一项基本技能。本项目......
  • React后台管理（十二）-- 页面常用hook封装 --- useSearch搜索封装
    文章目录前言一、useSearch自定义hook封装1.核心代码（1）hook文件代码+详细注释（2）使用到的store说明（3）使用到的config文件代码（4）使用到的白名单pageWhite文件代码2.使用方式（1）layout布局组件->监听并记录路由（2）搜索按钮组件->记录列表搜索的动作类型：搜索|重置（3）分页组件->记......
  • 赛克oj 1528（二叉搜索树）
    赛氪OJ-专注于算法竞赛的在线评测系统(saikr.com)题目描述小明初始的二叉搜索树是空树，他有一个长度为2∗......
  • 在Vision Pro 中如何把找圆区域直接赋值到斑点工具作为搜索区域
    文章目录概要整体架构流程技术细节小结概要项目需求：例如我们在项目中需要检测红圈与里面pin针的同心度（下附图），很显然红色的圆比较好找到，但是pin要抓到的话是有些不稳定的，下面我跟大家分享一个好用的项目经验。整体架构流程1.首先我们用找圆工具找到红的标注的圆2.下......
  • 代码随想录算法训练营第第20天 | 654.最大二叉树 、617.合并二叉树 、700.二叉搜索
    654.最大二叉树又是构造二叉树，昨天大家刚刚做完中序后序确定二叉树，今天做这个应该会容易一些，先看视频，好好体会一下为什么构造二叉树都是前序遍历题目链接/文章讲解：https://programmercarl.com/0654.最大二叉树.html视频讲解：https://www.bilibili.com/video/BV1MG411G7ox......
  • 二叉树的基本操作
    一、什么是二叉树：二叉树的介绍在上上章《数据结构-----堆的实现与操作》中有讲到，不知道的可以去那里看看二、二叉树的基本结构typedefintBTDataType;typedefstructBinaryTreeNode{ BTDataTypedata;//当前节点值域 structBinaryTreeNode*left;//指向当前节......
  • “二叉堆：不是，啊？”
    目录前言一、堆的概念及结构堆的性质：堆的结构:最大堆最小堆堆顶注意二、堆的实现1.初始化堆2.堆的插入什么是堆的向上调整算法？3.堆的删除什么是堆的向下调整算法？4.获取堆顶的数据5.获取堆的数据个数6.堆的判空7.堆的销毁三、建堆的时间复杂度四、堆排序五、二叉堆的......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99