Alibi

My Life is Getting Better

Leetcode[145] Binary Tree Postorder Traversal

11 Nov 2015

###Task1 Given a binary tree, return the postorder traversal of its nodes’ values.

For example: Given binary tree {1,#,2,3}, 1 \ 2 / 3 return [3,2,1].

Note: Recursive solution is trivial, could you do it iteratively?

###Python ####Recursive

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution(object):
    def postorderTraversal(self, root):
        """
        :type root: TreeNode
        :rtype: List[int]
        """
        if not root:
            return []
        ret = []
        self.post(root, ret)
        return ret
    def post(self, root, ret):
        if not root:
            return
        
        self.post(root.left, ret)
        self.post(root.right, ret)
        ret.append(root.val)

####Iterative

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution(object):
    def postorderTraversal(self, root):
        """
        :type root: TreeNode
        :rtype: List[int]
        """
        if not root:
            return []
        ret = []
        stack = []
        stack.append(root)
        prev = None
        while len(stack) > 0:
            cur = stack[-1]
            if not prev or prev.left == cur or prev.right == cur:
                if cur.left:
                    stack.append(cur.left)
                elif cur.right:
                    stack.append(cur.right)
                else:
                    ret.append(stack.pop().val)
            elif cur.left == prev:
                if cur.right:
                    stack.append(cur.right)
                else:
                    ret.append(stack.pop().val)
            elif cur.right == prev:
                ret.append(stack.pop().val)
            prev = cur
        return ret

###Java

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public ArrayList<Integer> postorderTraversal(TreeNode root) {
    	ArrayList<Integer> res = new ArrayList<Integer>();
    	Stack<TreeNode> stack = new Stack<TreeNode>();

    	if (root == null) {
    		return res;
    	}

        TreeNode prev = null;
        stack.push(root);
        while (!stack.isEmpty()) {
            TreeNode cur = stack.peek();
            if (prev == null || prev.left == cur || prev.right == cur) {
                if (cur.left != null) {
                    stack.push(cur.left);
                } else if (cur.right != null) {
                    stack.push(cur.right);
                } else {
                    stack.pop();
                    res.add(cur.val);
                }
            } else if (cur.left == prev) {
                if (cur.right != null) {
                    stack.push(cur.right);
                } else {
                    stack.pop();
                    res.add(cur.val);
                }
            } else if (cur.right == prev) {
                stack.pop();
                res.add(cur.val);
            }
            
            prev = cur;
        }

        return res;
    }
}

###Points

Related Posts