Question

Formatted question description: https://leetcode.ca/all/145.html

Given the root of a binary tree, return the postorder traversal of its nodes' values.

Example 1:

Input: root = [1,null,2,3]
Output: [3,2,1]

Example 2:

Input: root = []
Output: []

Example 3:

Input: root = [1]
Output: [1]

Constraints:

The number of the nodes in the tree is in the range [0, 100].
-100 <= Node.val <= 100

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

Algorithm

Since the order of post-order traversal is left-right-root, and the order of pre-order traversal is root-left-right, the two are actually very similar.

You can make some small changes in the method of pre-order traversal to make it work. The order becomes root-right-left, and then flipped, that is, left-right-root. The flip method is to add the result res in the reverse direction.

Each time, when adding to stack, left and then right, so that when the stack is processed, it is right and then left.

Code

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

public class Binary_Tree_Postorder_Traversal {

    /**
     * Definition for a binary tree node.
     * public class TreeNode {
     *     int val;
     *     TreeNode left;
     *     TreeNode right;
     *     TreeNode(int x) { val = x; }
     * }
     */
    public class Solution_two_stacks {
        public List<Integer> postorderTraversal(TreeNode root) {

            List<Integer> list = new ArrayList<>();

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

            Stack<TreeNode> sk = new Stack<>();
            Stack<TreeNode> reversedResult = new Stack<>();
            sk.push(root);

            while (!sk.isEmpty()) {
                TreeNode current = sk.pop();

                reversedResult.push(current);

                // @note:@memorize: left first then right. why? - right will be popped out first
                if (current.left != null) {
                    sk.push(current.left);
                }
                if (current.right != null) {
                    sk.push(current.right);
                }

            }

            // reversed to natural order
            while (!reversedResult.isEmpty()) {
                list.add(reversedResult.pop().val); // append to head of list
            }

            return list;

        }
    }

	public class Solution {
	    public List<Integer> postorderTraversal(TreeNode root) {

            ArrayList<Integer> list = new ArrayList<Integer>();

            // Check for empty tree
            if (root == null) {
                return list;
            }

            Stack<TreeNode> sk = new Stack<TreeNode>();
            sk.push(root);
            TreeNode prev = null;

            while (!sk.isEmpty()) {
                TreeNode current = sk.peek();

                /*
                 * go down the tree in search of a leaf if so process it and
                 * pop stack otherwise move down
                 */
                if (prev == null || prev.left == current || prev.right == current) {
                    if (current.left != null) {
                        sk.push(current.left);
                    } else if (current.right != null) {
                        sk.push(current.right);
                    } else { // left node here
                        sk.pop();
                        list.add(current.val);
                    }

                /*
                 * go up the tree from left node, if the child is right push
                 * it onto stack otherwise process parent and pop stack
                 */
                } else if (current.left == prev) {
                    if (current.right != null) {
                        sk.push(current.right);
                    } else {
                        sk.pop();
                        list.add(current.val);
                    }

                /*
                 * go up the tree from right node and after coming back from
                 * right node process parent and pop stack
                 */
                } else if (current.right == prev) {
                    sk.pop();
                    list.add(current.val);
                }

                prev = current;
            }

            return list;

	    }
	}

}

############

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public List<Integer> postorderTraversal(TreeNode root) {
        LinkedList<Integer> ans = new LinkedList<>();
        while (root != null) {
            if (root.right == null) {
                ans.addFirst(root.val);
                root = root.left;
            } else {
                TreeNode next = root.right;
                while (next.left != null && next.left != root) {
                    next = next.left;
                }
                if (next.left == null) {
                    ans.addFirst(root.val);
                    next.left = root;
                    root = root.right;
                } else {
                    next.left = null;
                    root = root.left;
                }
            }
        }
        return ans;
    }
}

// OJ: https://leetcode.com/problems/binary-tree-postorder-traversal/
// Time: O(N)
// Space: O(H)
class Solution {
private:
    vector<int> ans;
    void dfs(TreeNode* root) {
        if (!root) return;
        dfs(root->left);
        dfs(root->right);
        ans.push_back(root->val);
    }
public:
    vector<int> postorderTraversal(TreeNode* root) {
        dfs(root);
        return ans;
    }
};

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def postorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
        ans = []
        while root:
            if root.right is None:
                ans.append(root.val)
                root = root.left
            else:
                next = root.right
                while next.left and next.left != root:
                    next = next.left
                if next.left != root:
                    ans.append(root.val)
                    next.left = root
                    root = root.right
                else:
                    next.left = None
                    root = root.left
        return ans[::-1]

############

# 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]
    """
    res, stack = [], [(1, root)]
    while stack:
      p = stack.pop()
      if not p[1]:
        continue
      if p[0] == 0:
        res.append(p[1].val)
      else:
        stack.extend([(0, p[1]), (1, p[1].right), (1, p[1].left)])
    return res

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func postorderTraversal(root *TreeNode) []int {
	var ans []int
	for root != nil {
		if root.Right == nil {
			ans = append([]int{root.Val}, ans...)
			root = root.Left
		} else {
			next := root.Right
			for next.Left != nil && next.Left != root {
				next = next.Left
			}
			if next.Left == nil {
				ans = append([]int{root.Val}, ans...)
				next.Left = root
				root = root.Right
			} else {
				next.Left = nil
				root = root.Left
			}
		}
	}
	return ans
}

/**
 * Definition for a binary tree node.
 * class TreeNode {
 *     val: number
 *     left: TreeNode | null
 *     right: TreeNode | null
 *     constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
 *         this.val = (val===undefined ? 0 : val)
 *         this.left = (left===undefined ? null : left)
 *         this.right = (right===undefined ? null : right)
 *     }
 * }
 */

function postorderTraversal(root: TreeNode | null): number[] {
    if (root == null) return [];
    let stack = [];
    let ans = [];
    let prev = null;
    while (root || stack.length) {
        while (root) {
            stack.push(root);
            root = root.left;
        }
        root = stack.pop();
        if (!root.right || root.right == prev) {
            ans.push(root.val);
            prev = root;
            root = null;
        } else {
            stack.push(root);
            root = root.right;
        }
    }
    return ans;
}

// Definition for a binary tree node.
// #[derive(Debug, PartialEq, Eq)]
// pub struct TreeNode {
//   pub val: i32,
//   pub left: Option<Rc<RefCell<TreeNode>>>,
//   pub right: Option<Rc<RefCell<TreeNode>>>,
// }
//
// impl TreeNode {
//   #[inline]
//   pub fn new(val: i32) -> Self {
//     TreeNode {
//       val,
//       left: None,
//       right: None
//     }
//   }
// }
use std::rc::Rc;
use std::cell::RefCell;
impl Solution {
    fn dfs(root: &Option<Rc<RefCell<TreeNode>>>, res: &mut Vec<i32>) {
        if root.is_none() {
            return;
        }
        let node = root.as_ref().unwrap().borrow();
        Self::dfs(&node.left, res);
        Self::dfs(&node.right, res);
        res.push(node.val);
    }

    pub fn postorder_traversal(root: Option<Rc<RefCell<TreeNode>>>) -> Vec<i32> {
        let mut res = vec![];
        Self::dfs(&root, &mut res);
        res
    }
}

145 - Binary Tree Postorder Traversal

Question

Algorithm

Code

All Problems

All Solutions

Welcome to Subscribe On Youtube

Question

Algorithm

Code

All Problems

All Solutions