LeetCode Construct Binary Tree Traversal

105. Construct Binary Tree from Preorder and Inorder Traversal

Given preorder and inorder traversal of a tree, construct the binary tree.

Note: You may assume that duplicates do not exist in the tree.

方法

自己写的方法怎么都跑不通,郁闷,感觉逻辑没有错啊,先放上

public class Solution {
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        if(preorder==null||preorder.length == 0||inorder==null||inorder.length==0){
            return null;
        }
        return build(preorder,0,preorder.length-1,inorder,0,inorder.length-1);
    }
    public TreeNode build(int[] preorder, int pl, int pr, int[] inorder, int il, int ir){
        TreeNode tn = new TreeNode(preorder[pl]);
        if(pl == pr && il == ir){
            return tn;
        }
        int index = 0,pl2,pr2,il2,ir2;
        for(int i = 0;i <= ir; i++){
            if(inorder[i] == preorder[pl]){
                index = i;
                break;
            }
        }
        il = il;
        pl2 = pl+1;
        pl = pl + 1;
        pr2 = pr;
        pr = index;
        il2 = index+1;
        ir2 = ir;
        ir = index-1;
        if(pl <= pr && il <= ir)
            tn.left = build(preorder,pl,pr,inorder,il,ir);
        if(pl2 <= pr2 && il2 <= ir2)
            tn.right = build(preorder,pl2,pr2,inorder,il2,ir2);
        return tn;
    }
}

后面根据之前做剑指offer题目时的修改版本,修改之处为继续判断能否递归以是否在中序下节点左边的长度>0 或者节点右边的长度>0

public class Solution {
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        if(preorder==null||preorder.length == 0||inorder==null||inorder.length==0){
            return null;
        }
        return build(preorder,0,preorder.length-1,inorder,0,inorder.length-1);
    }
    public TreeNode build(int[] preorder, int pl, int pr, int[] inorder, int il, int ir){
        TreeNode tn = new TreeNode(preorder[pl]);
        if(pl == pr && il == ir){
            return tn;
        }
        int index = 0;
        for(int i = 0;i <= ir; i++){
            if(inorder[i] == preorder[pl]){
                index = i;
                break;
            }
        }
        int leftLength = index - il;
        int rightLength = ir - index;
        int leftPreEnd = pl + leftLength;
        if(leftLength > 0)
            tn.left = build(preorder,pl+1,leftPreEnd,inorder,il,index-1);
        if(rightLength > 0)
            tn.right = build(preorder,leftPreEnd+1,pr,inorder,index+1,ir);
        return tn;
    }
}

106. Construct Binary Tree from Inorder and Postorder Traversal

Given inorder and postorder traversal of a tree, construct the binary tree.

Note: You may assume that duplicates do not exist in the tree.

方法

实际上思路与上题类似,注意判断返回条件,以及中序和后序的起止点

public class Solution {
    public TreeNode buildTree(int[] inorder, int[] postorder) {
        if(inorder.length == 0 || postorder.length == 0){
            return null;
        }
        return build(inorder, 0, inorder.length-1, postorder, 0, postorder.length-1);
    }
    public TreeNode build(int[] inorder, int inl, int inr, int[] postorder, int pl, int pr){
        TreeNode root = new TreeNode(postorder[pr]);
        if(inl == inr && pl == pr && inorder[inl] == postorder[pl]){
            return root;
        }
        int index = 0;
        for(int i = inl; i <= inr; i++){
            if(inorder[i] == postorder[pr]){
                index = i;
                break;
            }
        }
        int leftlength = index - inl;
        int rightlength = inr - index;
        int prlength = pr - rightlength;
        if(leftlength > 0)
            root.left = build(inorder,inl,index-1,postorder,pl,pl+leftlength-1);
        if(rightlength > 0)
            root.right = build(inorder,index+1,inr,postorder,prlength,pr-1);
        return root;
    }
Share