Leetcode:105 & 106

Posted on

前序遍历：根-左-右
中序遍历：左-根-右
后序遍历：右-左-根
前序遍历和后续遍历可以确定根节点的位置（第一个或最后一个），中序遍历可以确定左子树上有哪些节点，右子树上有哪些节点。这两道题的大致思路就是通过前序或者后序遍历，确定根节点的位置，再通过中序遍历确定左右两边子树的节点，依次迭代。

105

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        return helper(0,0,inorder.length-1,preorder,inorder);
    }
    public TreeNode helper(int preStart,int inStart, int inEnd, int[] preorder, int[] inorder) {
        if(inStart>inEnd || preStart >= preorder.length) {return null;}
        // root
        TreeNode root = new TreeNode(preorder[preStart]);
        int index = 0;
        for(int i = index; i < inorder.length; i++) {
            if(inorder[i]==preorder[preStart]) {
                index = i;
                break;
            }
        }
        root.left = helper(preStart+1,inStart,index-1,preorder,inorder);
        root.right = helper(preStart+index-inStart+1,index+1,inEnd,preorder,inorder);
        return root;
    }
}

难点在于计算右子树的preStart。因为题中给出的例子左子树只有一个节点，容易忽略考虑左子树的长度。

106

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
    public TreeNode buildTree(int[] inorder, int[] postorder) {
        return helper(postorder.length-1,0,inorder.length-1,inorder,postorder);
    }
    public static TreeNode helper(int postEnd, int inStart, int inEnd, int[] inorder, int[] postorder) {
        if(postEnd>=postorder.length || inStart>inEnd) {return null;}
        TreeNode root = new TreeNode(postorder[postEnd]);
        int index = 0;
        for(int i = 0; i < inorder.length; i++) {
            if(inorder[i]==postorder[postEnd]) {
                index = i;
                break;
            }
        }
        root.left = helper(postEnd-inEnd+index-1,inStart,index-1,inorder,postorder);
        root.right = helper(postEnd-1,index+1,inEnd,inorder,postorder);
        return root;
    }
}

难点在于计算左子树的preStart。因为题中给出的例子左子树只有一个节点，容易忽略考虑左子树的长度。