day6-526互联

1、654 最大二叉树

递归法

构造树一般采用的是前序遍历，因为先构造中间节点，然后递归构造左子树和右子树。
递归三部曲
1. 确定递归函数的参数和返回值
  - 参数传入的是存放元素的数组，返回该数组构造的二叉树的头结点，返回类型是指向节点的指针。
2. 确定终止条件
3. 确定单层递归的逻辑
  - 先要找到数组中最大的值和对应的下标，最大的值构造根节点，下标用来下一步分割数组。
  - 最大值所在的下标的左边区间构造左子树
  - 最大值所在的下标的右边区间构造右子树

class Solution {
    public TreeNode constructMaximumBinaryTree(int[] nums) {
        if(nums.length == 0) {
            return null;
        }
        if(nums.length == 1) {
            TreeNode root = new TreeNode(nums[0]);
            return root;
        }

        int rootValue = Integer.MIN_VALUE;
        int rootIndex = 0;
        for(int i=0; i<nums.length; i++) {
            if(nums[i] > rootValue) {
                rootValue = nums[i];
                rootIndex = i;
            }
        }
        TreeNode root = new TreeNode(rootValue);

        int[] leftNums = Arrays.copyOfRange(nums, 0, rootIndex);
        root.left = constructMaximumBinaryTree(leftNums);
        
        int[] rightNums = Arrays.copyOfRange(nums, rootIndex+1, nums.length);
        root.right = constructMaximumBinaryTree(rightNums);

        return root;
    }   
}

以上代码比较冗余，效率也不高，每次还要切割的时候每次都要定义新的数组 ===> 优化：每次分隔不用定义新的数组，而是通过下标索引直接在原数组上操作。

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

    public TreeNode traversal(int[] nums, int left, int right) {// 在左闭右开区间[left, right)，构造二叉树
        if(left >= right) {
            return null;
        }

        int rootIndex = left;
        for(int i=rootIndex+1; i<right; i++) {
            if(nums[rootIndex] < nums[i]) {
                rootIndex = i;
            }
        }
        TreeNode root = new TreeNode(nums[rootIndex]);

        root.left = traversal(nums, left, rootIndex);
        root.right = traversal(nums, rootIndex+1, right);

        return root;
    }
}

2、617 合并二叉树

思路
1. 递归三部曲
  1. 确定递归函数的参数和返回值：
    - 首先要合入两个二叉树，那么参数至少是要传入两个二叉树的根节点，返回值就是合并之后二叉树的根节点。
  2. 确定终止条件：
    - 因为是传入了两个树，那么就有两个树遍历的节点t1 和 t2，如果t1 == NULL 了，两个树合并就应该是 t2 了（如果t2也为NULL也无所谓，合并之后就是NULL）。
    - 反过来如果t2 == NULL，那么两个数合并就是t1（如果t1也为NULL也无所谓，合并之后就是NULL）。
  3. 确定单层递归的逻辑：
    - 重复利用一下t1这个树，t1就是合并之后树的根节点（就是修改了原来树的结构）。
      - 单层递归中，就要把两棵树的元素加到一起。
      - t1 的左子树是：合并 t1左子树 t2左子树之后的左子树。
      - t1 的右子树：是合并 t1右子树 t2右子树之后的右子树。
    - 最终t1就是合并之后的根节点
```
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;
    }
}
```
2. 不重复利用已有树
```
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;
    }
}
```

3、700 二叉搜索树中的搜索

思路：二叉搜索树 ===> 有序

递归法

递归三部曲
1. 确定递归函数的参数和返回值
  - 递归函数的参数传入的就是根节点和要搜索的数值，返回的就是以这个搜索数值所在的节点。
2. 确定终止条件
  - 如果root为空，或者找到这个数值了，就返回root节点。
3. 确定单层递归的逻辑
  - 因为二叉搜索树的节点是有序的，所以可以有方向的去搜索。
  - 如果root->val > val，搜索左子树，
  - 如果root->val < val，就搜索右子树，
  - 最后如果都没有搜索到，就返回NULL。

代码1

class Solution {
    public TreeNode searchBST(TreeNode root, int val) {
        if(root == null || root.val == val) {
            return root;
        } 

        if(root.val > val) {
            return searchBST(root.left, val);
        } 
        if(root.val <val) {
            return searchBST(root.right, val);
        } 

        return null;

    }
}

代码2

class Solution {
    public TreeNode searchBST(TreeNode root, int val) {
        if(root == null || root.val == val) {
            return root;
        } 

        TreeNode res = null;
        if(root.val > val) {
            res = searchBST(root.left, val);
        } 
        if(root.val <val) {
            res = searchBST(root.right, val);
        } 

        return res;

    }
}

迭代法
- 思路：一提到二叉树遍历的迭代法，可能立刻想起使用栈来模拟深度遍历，使用队列来模拟广度遍历（层序遍历）。
- 对于二叉搜索树可就不一样了，因为二叉搜索树的特殊性，也就是节点的有序性，可以不使用辅助栈或者队列就可以写出迭代法。
- 对于一般二叉树，递归过程中还有回溯的过程，例如走一个左方向的分支走到头了，那么要调头，在走右分支。
- 而对于二叉搜索树，不需要回溯的过程，因为节点的有序性就帮我们确定了搜索的方向。
```
class Solution {
    public TreeNode searchBST(TreeNode root, int val) {
        while(root!=null) {
            if(root.val > val) {
                root = root.left;
            } else if(root.val < val) {
                root = root.right;
            } else {
                return root;
            }
        }
        return null;
    }
}
```

4、98 验证二叉搜索树

思路：
- 中序遍历下，输出的二叉搜索树节点的数值是有序序列。 ===> 遇到 搜索树，一定想着中序遍历，这样才能利用上特性。
递归法
- 递归三部曲
  1. 确定递归函数，返回值以及参数
    - 定义一个空节点，用于记录前一个节点，来比较遍历的节点是否有序
    - 递归函数要有bool类型的返回值，我们在寻找一个不符合条件的节点，如果没有找到这个节点就遍历了整个树，如果找到不符合的节点了，立刻返回。
  2. 确定终止条件
    - 遇到空结点，返回true【二叉搜索树也可以为空】
  3. 确定单层递归的逻辑
    - 中序遍历 ===> 利用搜索树中序遍历为有序序列的特性
    - 一直更新preNode，一旦发现preNode.val >= root.val，就返回false，注意元素相同时候也要返回false。
- 代码
```
class Solution {
    TreeNode preNode = null;// 用来记录前一个节点

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

        boolean left = isValidBST(root.left); //左

        if(preNode!= null && root.val <= preNode.val) {// 中序遍历，验证遍历的元素是不是从小到大
            return false;
        }
        preNode = root;// 记录前一个节点

        boolean right = isValidBST(root.right);//右

        return left&&right;

    }
}
```