[leetCode]Binary Tree Inorder Traversal 递归 && 栈解法

Given a binary tree, return the inorder traversal of its nodes' values.

For example:
Given binary tree {1,#,2,3},

return [1,3,2].

Note: Recursive solution is trivial, could you do it iteratively?

2种解法，一种是正常递归，另一种是使用栈思想

 1 #include <vector>
 2 #include <iostream>
 3 #include <stack>
 4 using namespace std;
 5 struct TreeNode {
 6     int val;
 7     TreeNode *left;
 8     TreeNode *right;
 9     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
10 };
11 class Solution {
12 public:
13     vector<int> valList;
14     vector<int> inorderTraversal1(TreeNode *root) {
15         InorderWalk(root);
16         return valList;
17     }
18     void  InorderWalk(TreeNode *root){
19         if(root == NULL) return;
20         TreeNode *cur = root;
21         if(cur->left != NULL) InorderWalk(cur->left);
22         valList.push_back(cur->val);
23         if(cur->right != NULL) InorderWalk(cur->right);        
24     }
25 }

第二种，使用堆栈。比较重要的函数是 SearchLeft(TreeNode *root)，他的作用是寻找一个在左子树上的叶子节点，并将路径上出现的节点压栈，若一条路径上没有左子树则将其加入输出队列(不知道解释清楚没)

中心思想大概可以理解为：有左边就(自己压栈再)走左边，没有左边就(自己输出再)走右边，左右都没有就输出自己。

1.若当前节点有左子树或右子树，或都有则进入2.否则表示当前节点为叶子节点，将其加入输出队列(valList)。

2.若当前节点(cur)有左子树(cur->left!=NULL)，将自己压栈，并走左子树(cur = cur->left)。再次判断1.

3.若当前节点没有左子树，则将自己加入输出队列(valList)中。再判断，若当前节点有右子树，走右子树，再次判断1.

 1     /**
 2 * Definition for binary tree
 3 * struct TreeNode {
 4 *     int val;
 5 *     TreeNode *left;
 6 *     TreeNode *right;
 7 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 8 * };
 9 */
10 #include <vector>
11 #include <iostream>
12 #include <stack>
13 using namespace std;
14 struct TreeNode {
15     int val;
16     TreeNode *left;
17     TreeNode *right;
18     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
19 };
20 class Solution {
21 public:
22     vector<int> valList;stack<TreeNode*> stk;
23     vector<int> inorderTraversal2(TreeNode *root) {//Iteratively    
24         valList.clear();
25         TreeNode *cur = root;
26         cur = SearchLeft(root);     
27         while(!stk.empty()){
28             cur = stk.top();
29             stk.pop();
30             valList.push_back(cur->val);
31             if(cur->right != NULL){
32                 cur = cur->right;
33                 cur = SearchLeft(cur);
34             }
35         }
36         return valList;
37     }
38 private:
39     TreeNode* SearchLeft(TreeNode *root){
40         if(root == NULL) return NULL;
41         TreeNode *cur = root;
42         while(cur->left !=NULL || cur->right != NULL){
43             if(cur->left != NULL){
44                 stk.push(cur);
45                 cur = cur->left;
46                 continue;
47             }
48             valList.push_back(cur->val);
49             cur = cur->right;
50         }
51         valList.push_back(cur->val);
52         return cur;
53     }

艰难的成长