[LintCode]二叉木の後順遍歴
13718 ワード
The recursive solution is trivial and I omit it here.
Iterative Solution using Stack (O(n) time and O(n) space):
Another sophisticated solution using Morris Traversal (O(n) time and O(1) space):
Iterative Solution using Stack (O(n) time and O(n) space):
1 /**
2 * Definition of TreeNode:
3 * class TreeNode {
4 * public:
5 * int val;
6 * TreeNode *left, *right;
7 * TreeNode(int val) {
8 * this->val = val;
9 * this->left = this->right = NULL;
10 * }
11 * }
12 */
13 class Solution {
14 /**
15 * @param root: The root of binary tree.
16 * @return: Postorder in vector which contains node values.
17 */
18 public:
19 vector<int> postorderTraversal(TreeNode *root) {
20 // write your code here
21 vector<int> nodes;
22 TreeNode* node = root;
23 TreeNode* lastNode = NULL;
24 stack<TreeNode*> toVisit;
25 while (node || !toVisit.empty()) {
26 if (node) {
27 toVisit.push(node);
28 node = node -> left;
29 }
30 else {
31 TreeNode* topNode = toVisit.top();
32 if (topNode -> right && topNode -> right != lastNode)
33 node = topNode -> right;
34 else {
35 nodes.push_back(topNode -> val);
36 lastNode = topNode;
37 toVisit.pop();
38 }
39 }
40 }
41 return nodes;
42 }
43 };
Another sophisticated solution using Morris Traversal (O(n) time and O(1) space):
1 /**
2 * Definition of TreeNode:
3 * class TreeNode {
4 * public:
5 * int val;
6 * TreeNode *left, *right;
7 * TreeNode(int val) {
8 * this->val = val;
9 * this->left = this->right = NULL;
10 * }
11 * }
12 */
13 class Solution {
14 /**
15 * @param root: The root of binary tree.
16 * @return: Postorder in vector which contains node values.
17 */
18 public:
19 vector<int> postorderTraversal(TreeNode *root) {
20 // write your code here
21 vector<int> nodes;
22 TreeNode* dump = new TreeNode(0);
23 dump -> left = root;
24 TreeNode* node = dump;
25 while (node) {
26 if (node -> left) {
27 TreeNode* predecessor = node -> left;
28 while (predecessor -> right && predecessor -> right != node)
29 predecessor = predecessor -> right;
30 if (!(predecessor -> right)) {
31 predecessor -> right = node;
32 node = node -> left;
33 }
34 else {
35 reverseAddNodes(node -> left, predecessor, nodes);
36 predecessor -> right = NULL;
37 node = node -> right;
38 }
39 }
40 else node = node -> right;
41 }
42 return nodes;
43 }
44 private:
45 void reverseNodes(TreeNode* start, TreeNode* end) {
46 TreeNode* x = start;
47 TreeNode* y = start -> right;
48 TreeNode* z;
49 while (x != end) {
50 z = y -> right;
51 y -> right = x;
52 x = y;
53 y = z;
54 }
55 }
56 void reverseAddNodes(TreeNode* start, TreeNode* end, vector<int>& nodes) {
57 reverseNodes(start, end);
58 TreeNode* node = end;
59 while (true) {
60 nodes.push_back(node -> val);
61 if (node == start) break;
62 node = node -> right;
63 }
64 reverseNodes(end, start);
65 }
66 };