算法训练营 day20 二叉树 最大二叉树 合并二叉树 二叉搜索树中的搜索 验证二叉树

最大二叉树

654. 最大二叉树 - 力扣LeetCode

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

创建一个根节点其值为 nums 中的最大值。
递归地在最大值 左边 的 子数组前缀上 构建左子树。
递归地在最大值 右边 的 子数组后缀上 构建右子树。
返回 nums 构建的 最大二叉树 。

最大二叉树的构建过程如下

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

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

参数传入的是存放元素的数组返回该数组构造的二叉树的头结点。

• 确定终止条件

题目中说了输入的数组大小一定是大于等于1的所以我们不用考虑小于1的情况那么当递归遍历的时候如果传入的数组大小为1说明遍历到了叶子节点了。

那么应该定义一个新的节点并把这个数组的数值赋给新的节点然后返回这个节点。 这表示一个数组大小是1的时候构造了一个新的节点并返回。

• 确定单层递归的逻辑

这里有三步工作

1. 先要找到数组中最大的值和对应的下标 最大的值构造根节点下标用来下一步分割数组。

2. 最大值所在的下标左区间 构造左子树

3. 最大值所在的下标右区间 构造右子树

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

    private TreeNode construct(int[] nums, int leftindex, int rightindex) {
        if (rightindex - leftindex < 1) {// 没有元素了
            return null;
        }
        if (rightindex - leftindex == 1) {// 只有一个元素
            return new TreeNode(nums[leftindex]);
        }
        int maxvalue = -1;
        int maxindex = 0;
        for (int i = leftindex;i<rightindex; i++){
            if (nums[i]>maxvalue){
                maxvalue = nums[i];
                maxindex = i;
            }
        }
        TreeNode node = new TreeNode(maxvalue);

        node.left = construct(nums,leftindex,maxindex);
        node.right = construct(nums,maxindex+1,rightindex);

        return node;
    }
}

合并二叉树

617. 合并二叉树 - 力扣LeetCode

给你两棵二叉树 root1 和 root2 。

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

返回合并后的二叉树。

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

递归法

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

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

2. 确定终止条件

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

反过来如果t2 == NULL那么两个数合并就是t1如果t1也为NULL也无所谓合并之后就是NULL。

3. 确定单层递归的逻辑

单层递归的逻辑就比较好写了这里我们重复利用一下t1这个树t1就是合并之后树的根节点就是修改了原来树的结构。

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

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

迭代法

class Solution {
    public TreeNode mergeTrees(TreeNode root1, TreeNode root2) {
        if (root1 == null) return root2;
        if (root2 == null) return root1;

        Stack<TreeNode> st = new Stack<>();
        st.push(root2);
        st.push(root1);
        while (!st.isEmpty()) {
            TreeNode node1 = st.pop();
            TreeNode node2 = st.pop();
            // 此时两个节点一定不为空val相加
            node1.val += node2.val;
            if (node1.left != null && node2.left != null) {// 如果两棵树左节点都不为空加入队列
                st.push(node2.left);
                st.push(node1.left);
            } else if (node1.left == null) {//当t1的左节点 为空 t2左节点不为空就赋值过去
                node1.left = node2.left;

            }
            if (node1.right != null && node2.right != null) {// 如果两棵树右节点都不为空加入队列
                st.push(node2.right);
                st.push(node1.right);
            } else if (node1.right == null) { // 当t1的右节点 为空 t2右节点不为空就赋值过去
                node1.right = node2.right;
            }
        }
        return root1;
    }
}

二叉搜索树中的搜索

700. 二叉搜索树中的搜索 - 力扣LeetCode

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

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

递归法

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

迭代法

class Solution {
    public TreeNode searchBST(TreeNode root, int val) {
        Stack<TreeNode> st = new Stack<>();
        if (root == null || root.val == val) return root;
        st.push(root);
        while (!st.isEmpty()) {
            TreeNode node = st.pop();
            if (node.val == val) {
                return node;
            }
            if (node.right != null) {
                st.push(node.right);
            }
            if (node.left != null) {
                st.push(node.left);
            }
        }
        return null;
    }
}


//迭代法 二叉搜索树的性质
class Solution {
    public TreeNode searchBST(TreeNode root, int val) {
        while (root != null) {
            if (root.val < val) root = root.right;
            else if (root.val > val) root = root.left;
            else return root;
        }
        return null;
    }
}

验证二叉搜索树

98. 验证二叉搜索树 - 力扣LeetCode

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

有效 二叉搜索树定义如下

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

这道题目比较容易陷入两个陷阱

• 陷阱1

不能单纯的比较左节点小于中间节点右节点大于中间节点就完事了。

我们要比较的是 左子树所有节点小于中间节点右子树所有节点大于中间节点。

节点10大于左节点5小于右节点15但右子树里出现了一个6 这就不符合了

• 陷阱2

样例中最小节点 可能是int的最小值如果这样使用最小的int来比较也是不行的。

递归法

class Solution {
    TreeNode node;
    public boolean isValidBST(TreeNode root) {
        if (root == null) return true;
        boolean left = isValidBST(root.left);
        if (node != null && root.val <= node.val)
            return false;
        node = root;
        boolean right = isValidBST(root.right);
        return left && right;
    }
}

迭代法

class Solution {
    long maxValue = Long.MIN_VALUE;
    public boolean isValidBST(TreeNode root) {
        Stack<TreeNode> st = new Stack<>();
        st.push(root);
        while (!st.isEmpty()){
            TreeNode node = st.pop();
            if (node!=null){
                if (node.right!=null) st.push(node.right);
                st.push(node);
                st.push(null);
                if (node.left!=null) st.push(node.left);
            }else {
                node = st.pop();
                if (node.val>maxValue){
                    maxValue = node.val;
                }else 
                    return false;
            }
        }
        return true;
     }
}