Iterative method, java


  • 0
    B
    public TreeNode buildTree(int[] in, int[] post) {
            if(in == null || post == null || in.length == 0 || post.length == 0 || in.length != post.length) return null;
            Stack<TreeNode> s = new Stack<TreeNode>();
            int i = in.length-1; 
            int j = post.length-1;
            TreeNode root = new TreeNode(post[j--]);
            s.push(root);
            TreeNode current = root, temp = null, right = null, left = null;
            while(i >= 0) {
                if(!s.isEmpty() && s.peek().val == in[i]) {
                    temp = s.pop();
                    i--;
                } else if(temp != null) {
                    left = new TreeNode(post[j--]);
                    s.push(left);
                    temp.left = left;
                    current = left;
                    temp = null;
                } else {
                    right = new TreeNode(post[j--]);
                    s.push(right);
                    current.right = right;
                    current = current.right;
                }
            }
            return root;
        }

  • 0
    Z

    I guess your code is right.
    But can you explain more about your logical


  • 0
    D

    For those who want to take a look at iterative method, you can read the paper

    Nonrecursive algorithms for constructing binary tree from its traversals


Log in to reply
 

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