[LintCode]二叉木の中順遍歴
10212 ワード
The recursive solution is trivial and I omit it here.
Iterative Solution using Stack (O(n) time and O(n) space):
Another more sophisticated soltuion 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: Inorder in vector which contains node values.
17 */
18 public:
19 vector<int> inorderTraversal(TreeNode *root) {
20 // write your code here
21 vector<int> nodes;
22 TreeNode* node = root;
23 stack<TreeNode*> toVisit;
24 while (node || !toVisit.empty()) {
25 if (node) {
26 toVisit.push(node);
27 node = node -> left;
28 }
29 else {
30 node = toVisit.top();
31 toVisit.pop();
32 nodes.push_back(node -> val);
33 node = node -> right;
34 }
35 }
36 return nodes;
37 }
38 };
Another more sophisticated soltuion 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: Inorder in vector which contains node values.
17 */
18 public:
19 vector<int> inorderTraversal(TreeNode *root) {
20 // write your code here
21 vector<int> nodes;
22 TreeNode* node = root;
23 while (node) {
24 if (node -> left) {
25 TreeNode* predecessor = node -> left;
26 while (predecessor -> right && predecessor -> right != node)
27 predecessor = predecessor -> right;
28 if (!(predecessor -> right)) {
29 predecessor -> right = node;
30 node = node -> left;
31 }
32 else {
33 predecessor -> right = NULL;
34 nodes.push_back(node -> val);
35 node = node -> right;
36 }
37 }
38 else {
39 nodes.push_back(node -> val);
40 node = node -> right;
41 }
42 }
43 return nodes;
44 }
45 };