java-代码随想录第十七天| 700.二叉搜索树中的搜索、617.合并二叉树、98.验证二叉搜索树

/**
 * 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;
        }
        if (val < root.val) {
            return searchBST(root.left, val);
        } else {
            return searchBST(root.right, val);
        }
    }
}

617.合并二叉树

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

题目：

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

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

返回合并后的二叉树。

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

题解：递归

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

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

2.确定终止条件

因为传入了两个树，有两个树遍历的节点t1和t2,如果t1==null,两个树合并就应该是t2了。（如果t2也为null，合并之后就是null）,反之亦然。

3.确定单层递归的逻辑

把两棵树的元素加在一起。

t1 的左子树：合并 t1左子树 t2左子树之后的左子树。

t1 的右子树：合并 t1右子树 t2右子树之后的右子树。

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

/**
 * 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) {
        //3 种相加的方式
        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;
        
    }
}

98.验证二叉搜索树

链接：98. 验证二叉搜索树 - 力扣（LeetCode）

题目：

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

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

节点的左子树只包含 严格小于 当前节点的数。

节点的右子树只包含 严格大于 当前节点的数。

所有左子树和右子树自身必须也是二叉搜索树。

题解：

给定一个二叉树，判断其是否是一个有效的二叉搜索树。

节点的左子树只包含小于当前节点的数。

节点的右子树只包含大于当前节点的数。

所有左子树和右子树自身必须也是二叉搜索树。

思路：在中序遍历下，输出的二叉搜索树节点的数值是有序序列

根据这个特性，验证二叉搜索树，判断一个序列是不是递增的。

/**
 * 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 max;
    public boolean isValidBST(TreeNode root) {
        if(root == null ){
            return true;
        }

        boolean left=isValidBST(root.left);

        //验证左子树是不是有效的BST,left==false,则立即返回false,不再检查当前节点和右子树。
        if(!left){
            return false;

        }

        //中 根节点的判断
        if(max != null && root.val <= max.val){
            return false;

        }
        max=root;

        //检查右子树
        boolean right=isValidBST(root.right);
        return right;
    }
}