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].
1 /** 2 * Definition for a binary tree node. 3 * public class TreeNode { 4 * public int val; 5 * public TreeNode left; 6 * public TreeNode right; 7 * public TreeNode(int x) { val = x; } 8 * } 9 */10 public class Solution {11 public IList PostorderTraversal(TreeNode root) {12 var result = new List ();13 if (root == null) return result;14 15 var stack = new Stack ();16 stack.Push(root);17 18 while (stack.Count > 0)19 {20 var p = stack.Pop();21 result.Insert(0, p.val);22 23 if (p.left != null)24 {25 stack.Push(p.left);26 }27 28 if (p.right != null)29 {30 stack.Push(p.right);31 }32 }33 34 35 return result;36 }37 38 }39 40 public class Solution2 {41 public IList PostorderTraversal(TreeNode root) {42 var result = new List ();43 if (root == null) return result;44 45 var stack = new Stack ();46 stack.Push(root);47 48 while (stack.Count > 0)49 {50 var p = stack.Peek();51 52 if (p.left != null)53 {54 stack.Push(p.left);55 p.left = null;56 }57 else if (p.right != null)58 {59 stack.Push(p.right);60 p.right = null;61 }62 else63 {64 stack.Pop();65 result.Add(p.val);66 }67 }68 69 70 return result;71 }72 73 }74 75 public class Solution1 {76 public IList PostorderTraversal(TreeNode root) {77 var result = new List ();78 DFS(root, result);79 return result;80 }81 82 private void DFS(TreeNode node, IList result)83 {84 if (node == null) return;85 DFS(node.left, result);86 DFS(node.right, result);87 result.Add(node.val);88 }89 }