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