算法笔记|Day15二叉树V

☆☆☆☆☆leetcode 654.最大二叉树

题目链接：leetcode 654.最大二叉树

题目分析

递归，采用前序遍历，构造中间节点，然后递归构造左子树和右子树。用数组构造二叉树，每次分隔通过下标索引直接在原数组上操作，这样可以节约时间和空间上的开销。

代码

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

    public TreeNode construct(int nums[],int left,int right){
        if(right-left<1)
            return null;
        if(right-left==1)
            return new TreeNode(nums[left]);
        int maxIndex=left;
        int maxVal=nums[maxIndex];
        for(int i=left;i<right;i++){
            if(nums[i]>maxVal){
                maxVal=nums[i];
                maxIndex=i;
            }
        }
        TreeNode root=new TreeNode(maxVal);
        root.left=construct(nums,left,maxIndex);
        root.right=construct(nums,maxIndex+1,right);
        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

提示：根据maxIndex划分左右子树。

☆☆☆☆☆leetcode 617.合并二叉树

题目链接：leetcode 617.合并二叉树

题目分析

递归，采用前序、中序、后序遍历均可，前序遍历更符合理解的逻辑。

代码

class Solution {
    public TreeNode mergeTrees(TreeNode root1, TreeNode root2) {
        TreeNode root=new TreeNode();
        if(root1==null)
            return root2;
        if(root2==null)
            return root1;
        root.val=root1.val+root2.val;
        root.left=mergeTrees(root1.left,root2.left);
        root.right=mergeTrees(root1.right,root2.right);
        return root;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13

提示：新建root，没有在root1和root2上直接做修改。

☆☆☆☆☆leetcode 700.二叉搜索树中的搜索

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

题目分析

二叉搜索树自带顺序，采用递归无需考虑前序、中序、后序遍历，另外可以使用迭代法层序遍历，根据平衡二叉树的特性判断向左还是向右迭代。

代码

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.right,val);
        if(root.val>val)
            return searchBST(root.left,val);
        return null;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12

2.迭代
class Solution {
    public TreeNode searchBST(TreeNode root, int val) {
        while(root!=null){
            if(root.val<val)
                root=root.right;
            else if(root.val>val)
                root=root.left;
            else
                return root;
        }
        return null;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

☆☆☆☆☆leetcode 98.验证二叉搜索树

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

题目分析

若采用中序遍历，可以把二叉树转换为一个数组，只需判断这个数组是否为有序数组。这里采用递归，用中序遍历，并用pre指针表示上一个节点，依次判断。

代码

class Solution {
    TreeNode pre;

    public boolean isValidBST(TreeNode root) {
        if(root==null)
            return true;
        if(isValidBST(root.left)==false)
            return false;
        if(pre!=null&&pre.val>=root.val)
            return false;
        pre=root;
        return isValidBST(root.right);
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14