代码随想录算法训练营day20 || 654.最大二叉树，617.合并二叉树，700.二叉搜索树中的搜索，98.验证二叉搜索树

视频讲解：

又是构造二叉树，又有很多坑！| LeetCode：654.最大二叉树_哔哩哔哩_bilibili

一起操作两个二叉树？有点懵！| LeetCode：617.合并二叉树_哔哩哔哩_bilibili

不愧是搜索树，这次搜索有方向了！| LeetCode：700.二叉搜索树中的搜索_哔哩哔哩_bilibili

你对二叉搜索树了解的还不够！ | LeetCode：98.验证二叉搜索树_哔哩哔哩_bilibili

654. 最大二叉树

其实关于昨天根据后序与中序遍历给出二叉树结构的题目，其核心与关键就是发掘后序遍历与中序遍历中的重合部分，找出这两部分中间节点的位置，从而由中序遍历的结果中定位左右子树的不同部分以及左右子树的节点数量。

我实现的时候，采用了四个数组分别保存中序遍历左右子树遍历的结果以及后序遍历左右子树遍历的结果，然后逐层细化左右子树范围，直至出现仅剩一个节点的子树范围，然后再逐层返回。其实使用双指针或者四个指针就可以实现原先的效果。（题目是105从前序与中序遍历序列构造二叉树）

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

// 时间复杂度O(n)，因为需要对inorder数组在每一次寻找根节点的时候都需要遍历一轮，但是遍历一次不会全部遍历n个元素，而是每一次一小部分，总共遍历一遍inorder数组
// 空间复杂度，O(1)，都是定义的变量进行辅助
class Solution {
    
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        
        return build(0, preorder.length-1, 0, inorder.length-1, preorder, inorder);
    }

    public TreeNode build(int prebegin, int preend, int inbegin, int inend, int[] preorder, int[] inorder){
        // left是先序序列的起始位置，right是后序序列操作的起始位置
        if(prebegin > preend && inbegin > inend)
            return null;
        
        int root_index = 0;

        // 优先定位根节点，总是先序遍历结果的首元素
        // prebegin就是先序遍历中根节点所在的节点的下标
        TreeNode root = new TreeNode(preorder[prebegin], null, null);
        
        // 在中序遍历的结果中找到，然后形成左右子树
        for(int i=inbegin; i <= inend; i++){
            if(inorder[i] == root.val){
                root_index = i;
                break;      // 由于树中不存在值重复的可能，所以这里可以直接break
            }
        }
        // 记录左右子树的长度，注意所有的长度以及左右子树信息的确定都是由中序遍历的结果来确定的
        int len_left = root_index - inbegin;
        int len_right = inend - root_index;

        if(len_left == 1)
            root.left = new TreeNode(preorder[prebegin+1], null, null);
        else if(len_left > 1)
            root.left = build(prebegin+1, prebegin+len_left, inbegin, root_index-1, preorder, inorder);
        else
            root.left = null;
        
        if(len_right == 1)
            root.right = new TreeNode(inorder[root_index+1], null, null);
        else if(len_right > 1)
            root.right = build(prebegin+len_left+1, preend, root_index+1, inend, preorder, inorder);
        else
            root.right = null;

        return root;
    }
}

思路：本题的思路在于不断寻找当前范围内的最大值，作为局部根节点，然后利用所分割出来的左右区域，为根结点的left与right部分进行填充，不断重复此过程，直到最上层的根节点的left与right部分被填充完成。另外关于 “为什么构建二叉树的时候都是先序遍历的操作？” 这个问题，在我看来构建二叉树时，首先是构造节点，其实是填充左右子树；题目中不会给出二叉树的根结点，换言之需要从根结点开始逐层的构建二叉树，因此开始的时候这棵树上没有任何一个节点，没有任何节点那么自然优先访问作子树以及左右子树的中序与后序遍历会不可行。

看了 1ms 时间开销的解法，其中是将getMax的操作放在了递归体之中，然后在递归体之中再给出左子树与右子树的范围指针，共四个指针。但是总体的思路而言与本题给出的解答几乎一致。

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

// 时间复杂度o(n)，因为寻找最大元素的过程总体就是访问了一遍nums，而访问的过程是伴随着逐次的递归进行的，nums访问完，递归也就结束了
// 空间复杂度O(1)

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

    public TreeNode DFS(int[] nums, int begin, int end){
        if(begin == end)
            return null;
        // 确定当前数组范围内最大元素的下标
        // 回答代码随想录本题题解中的问题：为什么构建二叉树的时候都是先序遍历的操作，在我看来构建二叉树时，首先是构造节点，其实是填充左右子树；
        // 题目中不会给出二叉树的根结点，换言之需要从根结点开始逐层的构建二叉树，因此开始的时候这棵树上没有任何一个节点，没有任何节点那么自然优先访问作子树以及左右子树的中序与后序遍历会不可行

        // 根操作
        int index = getMax(nums, begin, end);
        TreeNode node = new TreeNode(nums[index], null, null);

        // 左右操作
        node.left = DFS(nums, begin, index);
        node.right = DFS(nums, index+1, end);

        return node;
    }

    public int getMax(int[] nums, int begin, int end){
        int max = begin;
        for(int i=begin+1; i<end; i++){
            if(nums[i] > nums[max])
                max = i;
        }

        return max;
    }
}

617. 合并二叉树

思路：从题意上理解，本题的解题思路就是挑选任意一种遍历方式，然后让两棵树使用同一种遍历方式进行遍历，其次需要注意的就是额外的需要判断当前节点有无左右子树，这关乎到要节点之间的拼接。另外时间复杂度上，只需要对root1的所有位置进行一遍考察就行，不存在的地方用root2进行填补也是在考察的过程中进行的，因此时间复杂度就是使用递归遍历root1所花费的时间。

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

// 时间复杂度O(n)，n是root1的节点数量
// 空间复杂度O(1)
class Solution {
    public TreeNode mergeTrees(TreeNode root1, TreeNode root2) {
        // 从题意上理解，本题的解题思路就是挑选任意一种遍历方式，然后让两棵树使用同一种遍历方式进行遍历
        // 其次需要注意的就是额外的需要判断当前节点有无左右子树，这关乎到要节点之间的拼接

        // 将root1作为结果树，因此需要额外考虑root1不存在，root2随便存不存在这种特殊情况
        if(root1 == null && root2 != null)
            return root2;
           
        DFS(root1, root2);

        return root1;
    }
    // 补充一个个人理解的点，深度优先是先序、中序、后序三种树的遍历的有效载体，而层次遍历是全新的树的遍历策略，与先序、中序、后序都不一样
    // 因此我在解题时，如果觉察本题是要用到先序、中序或者后序此类遍历方法，那么我总是使用深度优先策略，都不行的话，就使用层次遍历；当然有时候层次遍历也是可以直接呼之欲出，
    public void DFS(TreeNode t1, TreeNode t2){
        if(t1 == null || t2 == null)
            return;
        
        // 先序遍历解题，因为先序遍历可以优先的站在父节点上去判断左右子树是否需要拼接；然后从题目中的树的拼接顺序来看，也是从根节点开始逐层向下拼接的
        // 根
        t1.val = t1.val + t2.val;   // t1，t2都不是null
        
        // 左右
        if(t1.left != null && t2.left != null)
            DFS(t1.left, t2.left);
        else if(t1.left == null && t2.left != null)
            t1.left = t2.left;
        else
            DFS(t1.left, t2.left);

        // 其他的t1.left不为空，但t2.left为空，无需对t1这棵结果树进行操作，所以不用额外的判断

        if(t1.right != null && t2.right != null)
            DFS(t1.right, t2.right);
        else if(t1.right == null && t2.right != null)
            t1.right = t2.right;
        else
            DFS(t1.right, t2.right);
        
        return;
    }

}

700. 二叉搜索树中的搜索

思路：直接遍历搜索也就可以解题，结合二叉搜索树的特点可进一步优化遍历的开销。

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

// 时间复杂度O(n)
// 空间复杂度O(1)

class Solution {
    public TreeNode searchBST(TreeNode root, int val) {
        return DFS(root, val);
    }

    // 利用二叉搜索树的特点，根节点左子树全部小于根节点，右子树全部大于根节点，二叉搜索树等同于二分查找的可视化过程
    public TreeNode DFS(TreeNode t, int val){
        if(t == null)
            return null;
        
        // 这里每种情况是一个return，因为我们是从root开始进行递归的，root节点的操作就是最后需要返回的结果，所以每一个部分都是一个return
        // 并且再结合二叉搜索树的特点，左右子树的操作是可以完全独立的
        if(t.val == val)
            return t;
        else if(t.val > val)
            return DFS(t.left, val);
        else
            return DFS(t.right, val);
    }
}

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;
 *     }
 * }
 */
// 时间复杂度O(n)
// 空间复杂度O(n)

class Solution {
    public boolean isValidBST(TreeNode root) {
        
        // 二叉搜索树的中序遍历结果一定是有序的序列，基于此进行求解
        List<Integer> list = new ArrayList<>();
        boolean flag = true;
        inOrderTraversal(root, list);
        for(int i=0; i<list.size()-1; i++)
            if(list.get(i) >= list.get(i+1))
                flag = false;
        return flag;
    }

    public void inOrderTraversal(TreeNode t, List<Integer> list){
        if(t == null)
            return;
        
        inOrderTraversal(t.left, list);
        list.add(t.val);
        inOrderTraversal(t.right, list);

        return;
    }
        
}