654.最大二叉树

文章：19. 最大二叉树

题目：654. 最大二叉树

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

【思路】

构造二叉树类型的题目，我们都使用前序遍历对二叉树进行构造。

先构造中间节点，再构造左子树，最构造右子树

递归

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

2.确定终止条件

  • 当传入的数组大小为1的时候，说明遍历到了叶子节点
  • 那么应该定义一个新节点，把这个数组的数值赋给新的节点，然后返回这个节点。

3.确定单层递归的逻辑

  • 先找到数组中最大值和对应的下标，最大的值构造根节点，下标用来下一步分割数组。
  • 最大值所在的下标左区间 构造左子树
  • 最大值所在的下标右区间 构造右子树
  • Java实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
    public TreeNode constructMaximumBinaryTree(int[] nums) {
        return traversal(nums,0,nums.length);
    }
    public TreeNode traversal(int[] nums,int s,int e){
        if(s >= e)return null;
        int maxIndex = s;
        for(int i = s+1 ;i <e;i++){
            if(nums[i] > nums[maxIndex]) maxIndex = i;
        }
        TreeNode n = new TreeNode(nums[maxIndex]);

        n.left = traversal(nums,s,maxIndex);
        n.right = traversal(nums,maxIndex+1,e);
        return n;
        
    }
}
  • Go实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
func constructMaximumBinaryTree(nums []int) *TreeNode {
    //递归
    return traversal(nums)
}
func traversal(nums []int)*TreeNode{
    if len(nums)==0{
        return nil
    }
    maxIndex := 0
    for i,n := range nums{
        if n > nums[maxIndex]{
            maxIndex = i
        }
    }
    //切割数组
    root := &TreeNode{Val: nums[maxIndex]}
    root.Left = traversal(nums[:maxIndex])//这里的maxIndex代表的是数组长度，nums[maxIndex]为空
    root.Right = traversal(nums[maxIndex+1:])
    return root
}

617.合并二叉树

文章：21. 合并二叉树

题目：617. 合并二叉树

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

【思路】

使用前序遍历。一开始通过root1和root2是否为空作为判断条件，有效的解决了出现如果root1或root2为空&&root1==null &&root2==null，然后通过递归来获取左子树和右子树。

  • Java实现
1
2
3
4
5
6
7
8
9
10
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;
    }
}
  • Go实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
func mergeTrees(root1 *TreeNode, root2 *TreeNode) *TreeNode {
    if root1 == nil{
        return root2
    }
    if root2 == nil{
        return root1
    }
    /*root := &TreeNode{Val: root1.Val + root2.Val}
    root.Left = mergeTrees(root1.Left,root2.Left)
    root.Right = mergeTrees(root1.Right,root2.Right)*/
    //直接在原树上修改
    root1.Val += root2.Val
    root1.Left = mergeTrees(root1.Left,root2.Left)
    root1.Right = mergeTrees(root1.Right,root2.Right)
    return root1
}

700.二叉搜索树中的搜索

文章：22. 二叉搜索树中的搜索

题目：700. 二叉搜索树中的搜索

【思路】

二叉搜索树是一个有序树

  • 若它的左子树不为空，则左子树上所有节点的值均小于它的根节点的值
  • 若它的右子树不为空，则柚子树上所有系欸但的值均大于它的根节点的值
  • 它的左、右子树也分别为二叉搜索树

需要新建一个变量来承接递归后的值，而不是修改原来的root节点。

  • Java实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
    public TreeNode searchBST(TreeNode root, int val) {
        if(root == null || root.val == val)return root;
        TreeNode result = new TreeNode();
        if(root.val > val){
            result = searchBST(root.left,val);
        }
        if(root.val < val){
            result = searchBST(root.right,val);
        }
        
        return result;
    }
}
  • Go实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
func searchBST(root *TreeNode, val int) *TreeNode {
    if root == nil || root.Val == val{
        return root
    }
    // **需要新建一个变量来承接递归后的值，而不是修改原来的root节点。**
    node := &TreeNode{}

    //如果当前节点 大于val
    if root.Val >val{
        node = searchBST(root.Left,val)
    }
    if root.Val < val {
        node = searchBST(root.Right,val)
    }
    return node
}

23.验证二叉搜索树

文章：23. 验证二叉搜索树

题目：98. 验证二叉搜索树

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

【思路】

二编：同样犯了只判断当前节点的问题，判断的应该是整个搜索树最小和最大的值，类似双指针，每层递归不断更新最大最小值

误区：只判断了 if root.Left.Val >= root.Val || root.Right.Val < root.Val，而忽略了二叉搜索树的根节点也大于左子树的全部节点，小于右子树的全部节点

  • Java实现（不是很理解

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    class Solution {
        long prev = Long.MIN_VALUE;
        public boolean isValidBST(TreeNode root) {
            if(root == null)return true;
            //中序遍历
            if(!isValidBST(root.left))return false;
            if(root.val <= prev){
                return false;
            }
            prev = root.val;
            return isValidBST(root.right);

        }
    }

  • Go实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
func isValidBST(root *TreeNode) bool {
    if root == nil{
        return true
    }
    return traversal(root,math.MinInt64,math.MaxInt64)
}
func traversal(root *TreeNode,min,max int64)bool{
    if root == nil{
        return true
    }
    //判断当前节点,只要存在其中一个不满足条件就返回false
    if max<= int64(root.Val) || min >= int64(root.Val){
        return false
    }

    return traversal(root.Left,min,int64(root.Val)) && traversal(root.Right,int64(root.Val),max)
}

【算法总结】

  • 最大二叉树：构造二叉树类型的题目，我们都使用前序遍历对二叉树进行构造。

  • 合并二叉树：递归实现

  • 二叉搜索树中的搜索：递归实现，需要新建一个变量来承接递归后的值，而不是修改原来的root节点。

  • 验证二叉搜索树：

    • 误区：只判断了 if root.Left.Val >= root.Val || root.Right.Val < root.Val，而忽略了二叉搜索树的
    • java 中序遍历，go 迭代