LeetCode | Binary Tree Postorder Traversal

题目

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

题目说了，递归太简单，有本事整个非递归的。

二叉树的先序、中序、后序三种遍历方式中，后序遍历的非递归实现稍微复杂些，需要额外开辟空间记录每个节点的右孩子是否已经访问。

代码

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

public class BinaryTreePostorderTraversal {
	public class TreeNode {
		int val;
		TreeNode left;
		TreeNode right;

		TreeNode(int x) {
			val = x;
		}
	}

	public ArrayList
  
    postorderTraversal(TreeNode root) {
		ArrayList
   
     list = new ArrayList
    
     (); // recursivePostorderTraversal(root, list); iterativePostorderTraversal(root, list); return list; } class TreeNodeWithFlag { TreeNode node; boolean isVisited; TreeNodeWithFlag(TreeNode node, boolean isVisited) { this.node = node; this.isVisited = isVisited; } } private void iterativePostorderTraversal(TreeNode root, ArrayList
     
       list) { if (root == null) { return; } Stack
      
        stack = new Stack
       
        (); TreeNode node = root; while (node != null) { stack.push(new TreeNodeWithFlag(node, false)); node = node.left; } while (!stack.isEmpty()) { TreeNodeWithFlag nodeWithFlag = stack.peek(); node = nodeWithFlag.node; if (node.right == null || nodeWithFlag.isVisited) { nodeWithFlag = stack.pop(); list.add(nodeWithFlag.node.val); } else { nodeWithFlag.isVisited = true; node = node.right; while (node != null) { stack.push(new TreeNodeWithFlag(node, false)); node = node.left; } } } } private void recursivePostorderTraversal(TreeNode root, ArrayList
        
          list) { if (root == null) { return; } recursivePostorderTraversal(root.left, list); recursivePostorderTraversal(root.right, list); list.add(root.val); } }