67 二叉树的中序遍历

原题网址：http://www.lintcode.com/zh-cn/problem/binary-tree-inorder-traversal/#

给出一棵二叉树,返回其中序遍历

您在真实的面试中是否遇到过这个题？

Yes

样例

给出二叉树 {1,#,2,3},

返回 [1,3,2].

挑战

你能使用非递归算法来实现么?

标签

二叉树递归微软二叉树遍历

1、递归

 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: A Tree
18      * @return: Inorder in ArrayList which contains node values.
19      */
20      vector<int> result;
21     vector<int> inorderTraversal(TreeNode * root) {
22         // write your code here
23         if (root!=NULL)
24     {
25         inorderTraversal(root->left);
26         result.push_back(root->val);
27         inorderTraversal(root->right);
28     }
29     return result;
30     }
31 };

2、非递归

写循环写到快吐血就知道递归的好处了……

中序遍历：左根右

先找到最左面的叶子结点，同时保存根节点，找到之后push到结果数组中；

然后判断当前节点还有没有右节点，有的话赋值给移动指针继续左根右的顺序遍历，没有右节点并且根节点栈不为空的情况下，弹出栈顶，根节点数值push到结果数组中，删除栈顶，然后再判断是否有右节点（当然要判断了，已经处理左和根，右也不能跑），没有的话继续弹出栈、赋值、删除栈、判断是否有右节点，OK，又一个循环……

如果既没有右节点，栈也为空，break跳出循环。注意！p是不可能为NULL的，靠它结束循环是行不通的……

 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: A Tree
18      * @return: Inorder in ArrayList which contains node values.
19      */
20     vector<int> inorderTraversal(TreeNode * root) {
21         // write your code here
22         vector<int> result;
23     stack<TreeNode*> temp;
24     TreeNode *p=root;
25     while(p!=NULL)
26     {
27             if (p->left!=NULL)
28             {
29                 temp.push(p);
30                 p=p->left;
31                 continue;
32             }
33 
34             result.push_back(p->val); 
35 
36             if (p->right!=NULL)
37             {
38                 p=p->right;
39             }
40             else if (!temp.empty()) 
41             {
42                 p=temp.top();
43                 result.push_back(p->val);
44                 temp.pop();
45                 p=p->right; //右节点可能不存在？;
46                 while(p==NULL&&temp.size()!=0)
47                 {
48                     p=temp.top();
49                     result.push_back(p->val);
50                     temp.pop();
51                     p=p->right;
52                 }
53             }  
54         else
55         {
56             break;
57         }
58     }
59     return result;
60     }
61 };

非递归方法还有更简洁的代码，请参考：https://blog.csdn.net/chan15/article/details/48832421

 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: A Tree
18      * @return: Inorder in ArrayList which contains node values.
19      */
20     vector<int> inorderTraversal(TreeNode * root) {
21         // write your code here
22         vector<int> result;
23     stack<TreeNode*> temp;
24     TreeNode *p=root;
25     while(p!=NULL||!temp.empty())
26     {
27         while (p!=NULL)
28         {
29             temp.push(p);
30             p=p->left;
31         }
32         p=temp.top();
33         temp.pop();
34         result.push_back(p->val);
35         p=p->right;
36     }
37     return result;
38     }
39 };