[LintCode] 二叉树的中序遍历-阿里云开发者社区

[LintCode] 二叉树的中序遍历

2015-06-29 848

版权

本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。

简介： The recursive solution is trivial and I omit it here. Iterative Solution using Stack (O(n) time and O(n) space): 1 /** 2 * Definition of TreeN...

The recursive solution is trivial and I omit it here.

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 };