LeetCode: Binary Tree Postorder Traversal

跟inorder差不多

 1 /**
 2  * Definition for binary tree
 3  * struct TreeNode {
 4  *     int val;
 5  *     TreeNode *left;
 6  *     TreeNode *right;
 7  *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 8  * };
 9  */
10 class Solution {
11 public:
12     vector<int> postorderTraversal(TreeNode *root) {
13         vector<int> res;
14         stack<TreeNode *> S;
15         if (!root) return res;
16         S.push(root);
17         while (!S.empty()) {
18             TreeNode *top = S.top();
19             if (!top->left && !top->right) {
20                 res.push_back(top->val);
21                 S.pop();
22             }
23             else {
24                 if (top->right) {
25                     S.push(top->right);
26                     top->right = NULL;
27                 }
28                 if (top->left) {
29                     S.push(top->left);
30                     top->left = NULL;
31                 }
32             }
33         }
34         return res;
35     }
36 };

 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 List<int> PostorderTraversal(TreeNode root) {
12         List<int> ans = new List<int>();
13         Stack<TreeNode> S = new Stack<TreeNode>();
14         if (root == null) return ans;
15         S.Push(root);
16         while (S.Count > 0) {
17             TreeNode peek = S.Peek();
18             if (peek.left == null && peek.right == null) {
19                 ans.Add(peek.val);
20                 S.Pop();
21             }
22             else {
23                 if (peek.right != null) {
24                     S.Push(peek.right);
25                     peek.right = null;
26                 }
27                 if (peek.left != null) {
28                     S.Push(peek.left);
29                     peek.left = null;
30                 }
31             }
32         }
33         return ans;
34     }
35 }

View Code