Beat 97% JAVA Iterative Solution.


  • 1
    R
    public class Solution {
        public TreeNode buildTree(int[] preorder, int[] inorder) {
            int len = preorder.length;
            if(preorder==null||len == 0){
                return null;
            }
            TreeNode[] stack = new TreeNode[len];
            boolean[] flag = new boolean[len];
            int k=-1, unSee=-1;
            for(int i = 0, j = 0 ; i < len||j<len ;){
                if(k<0){
                    k++;
                    stack[k] = new TreeNode(preorder[i]);
                    flag[k] = false;
                    unSee++;
                    i++;
                }else{
                    if(unSee>=0&&inorder[j] == stack[unSee].val){
                        for(int x = unSee; x < k; x++){
                            if(x==unSee){
                                stack[x].left = stack[x+1];
                            }else{
                                stack[x].right = stack[x+1];
                            }
                        }
                        k = unSee;
                        flag[unSee] = true;
                        j++;
                        while(unSee>=0&&flag[unSee]==true){
                            unSee--;
                        }
                    }else{
                        k++;
                        stack[k] = new TreeNode(preorder[i]);
                        flag[k] = false;
                        unSee = k;
                        i++;
                    }
                }
            }
            for(int i = 0; i<k; i++){
                stack[i].right = stack[i+1];
            }
            return stack[0];
        }
    }

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.