算法训练（leetcode）二刷第十五天 | 654. 最大二叉树、617. 合并二叉树、700. 二叉搜索树中的搜索、98. 验证二叉搜索树

654. 最大二叉树

leetcode题目地址

递归建树。

时间复杂度： $O(n)$
空间复杂度： $O(n)$

// java
/**
 * 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 buildTree(int[] nums, int left, int right){
    	// 左右闭区间
        if(right<left) return null;
        int maxIdx = left;
        for(int i=left+1; i<=right; i++){
            if(nums[i]>nums[maxIdx]) maxIdx=i;
        }
        TreeNode root = new TreeNode(nums[maxIdx]);
        root.left = buildTree(nums, left, maxIdx-1);
        root.right = buildTree(nums, maxIdx+1, right);
        return root;

    }
    public TreeNode constructMaximumBinaryTree(int[] nums) {
        return buildTree(nums, 0, nums.length-1);
    }
}

617. 合并二叉树

leetcode题目地址

同上题，递归建树。

时间复杂度： $O(n)$
空间复杂度： $O(n)$

// java
/**
 * 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 getResultTree(TreeNode root1, TreeNode root2) {
        
        if(root1 == null && root2 == null) return null;
        TreeNode node = new TreeNode();
        // 左空右不空
        if(root1 == null) {
            node.val = root2.val;
            node.left = getResultTree(root1, root2.left);
            node.right = getResultTree(root1, root2.right);
            return node;
        } else if(root2 == null) {
             // 左不空右空
            node.val = root1.val;
            node.left = getResultTree(root1.left, root2);
            node.right = getResultTree(root1.right, root2);
            return node; 
        }else{
            node.val = root1.val + root2.val;
            node.left = getResultTree(root1.left, root2.left);
            node.right = getResultTree(root1.right, root2.right);
            return node; 
        }
        
    }
    public TreeNode mergeTrees(TreeNode root1, TreeNode root2) {
        return getResultTree(root1, root2);
    }
}

700. 二叉搜索树中的搜索

leetcode题目地址

二叉搜索树中进行搜索就是一个二分查找的过程。

时间复杂度： $O(n)$
空间复杂度： $O(n)$

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

98. 验证二叉搜索树

leetcode题目地址

二叉搜索树的中序遍历序列是单调递增的，因此借助中序遍历，若出现后一个元素小于前一个元素则为false。

时间复杂度： $O(n)$
空间复杂度： $O(n)$

写法一

// java
/**
 * 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 {
    private TreeNode pre;
    private boolean flag;
    public void inOrder(TreeNode root){
        if(!this.flag) return;
        if(root.left != null) inOrder(root.left);
        if(pre!=null && root.val <= pre.val) flag = false;
        pre = root;
        if(root.right != null) inOrder(root.right);
    }
    public boolean isValidBST(TreeNode root) {
        this.pre = null;
        this.flag = true;
        if(root == null) return true;
        inOrder(root);
        return this.flag;
    }
}

写法二

// java
/**
 * 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 {
    private TreeNode pre;
    public boolean inOrder(TreeNode root){
        if(root == null) return true;
        // 左
        boolean left = inOrder(root.left);
        if(!left) return false;
        // 中
        if(pre != null && root.val<=pre.val) return false;
        pre = root;
        // 右
        boolean right = inOrder(root.right);
        if(!right) return false;

        return true;
    }
    public boolean isValidBST(TreeNode root) {
        this.pre = null;
        if(root == null) return true;
        return inOrder(root);
    }
}