20-算法训练营第二十天 |力扣654最大二叉树、力扣617合并二叉树、力扣98验证二叉搜索树

力扣654：最大二叉树

题目链接:力扣654：最大二叉树

---

思路：

1.构造二叉树一定是采用前序遍历
2.确定递归参数（nums，0，nums.length）
3.确定递归终止条件（当没有元素时或者只有一个元素）
4.确定每层递归逻辑（先找到最大值的下标，然后进行切割成左右数组递归传递下标值）

---

代码：

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

    public TreeNode constructMaximumBinaryTree1(int[] nums, int leftIndex, int rightIndex) {
        if (rightIndex - leftIndex < 1) {// 没有元素了
            return null;
        }
        if (rightIndex - leftIndex == 1) {// 只有一个元素
            return new TreeNode(nums[leftIndex]);
        }
        int maxIndex = leftIndex;// 最大值所在位置
        int maxVal = nums[maxIndex];// 最大值
        for (int i = leftIndex + 1; i < rightIndex; i++) {
            if (nums[i] > maxVal){
                maxVal = nums[i];
                maxIndex = i;
            }
        }
        TreeNode root = new TreeNode(maxVal);
        // 根据maxIndex划分左右子树
        root.left = constructMaximumBinaryTree1(nums, leftIndex, maxIndex);
        root.right = constructMaximumBinaryTree1(nums, maxIndex + 1, rightIndex);
        return root;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

---

力扣617：合并二叉树

题目链接:力扣617：合并二叉树

---

思路：

1.递归法(前序遍历)
2.确定递归参数(跟题中一致)
3.定递归终止条件
4.确定每层递归逻辑

---

代码：

class Solution {
    public TreeNode mergeTrees(TreeNode root1, TreeNode root2) {
        // 递归法(前序遍历)
        // 确定递归参数(跟题中一致)
        // 确定递归终止条件
        if (root1 == null) {
            return root2;
        }
        if (root2 == null) {
            return root1;
        }
        // 确定每层递归逻辑
        root1.val = root1.val + root2.val;
        root1.left = mergeTrees(root1.left, root2.left);
        root1.right = mergeTrees(root1.right, root2.right);
        return root1;
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

---

力扣700：二叉搜索树中的搜索

题目链接:力扣700：二叉搜索树中的搜索

---

思路：

1.采用递归法(前序遍历)
2.确定递归参数(跟题中保持一致)
3.确定递归终止条件
4.确定每层递归逻辑

---

代码：

class Solution {
    public TreeNode searchBST(TreeNode root, int val) {
        // 采用递归法(前序遍历)
        // 确定递归参数(跟题中保持一致)
        // 确定递归终止条件
        TreeNode result = null;
        if (root == null || root.val == val) {
            return root;
        }
        // 确定每层递归逻辑
        if (root.val < val) {
            result = searchBST(root.right, val);
        }
        if (root.val > val) {
            result = searchBST(root.left, val);
        }

        return result;
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

---

力扣98：验证二叉搜索树

题目链接:力扣98：验证二叉搜索树

---

思路：

1.定义一个指针，用于指向下一个元素
2.采用递归法(中序遍历)
3.确定递归参数，跟题中保持一致
4.确定终止条件
5.确定每层递归逻辑

---

代码：

class Solution {
    // 定义一个指针，用于指向下一个元素
    TreeNode pre;
    public boolean isValidBST(TreeNode root) {
        // 采用递归法(中序遍历)
        // 确定递归参数，跟题中保持一致
        // 确定终止条件
        if (root == null) {
            return true;
        }
        // 确定每层递归逻辑
        boolean left = isValidBST(root.left);
        if (pre != null && pre.val >= root.val) {
            return false;
        }
        pre = root;
        boolean right = isValidBST(root.right);
        return left && right;
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21