94. Binary Tree Inorder Traversal （easy) !!!!!!!!!!!!!!!!!!!!!!!! 迭代的方法要仔细体会

Q:

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

 

Example 1:

Input: root = [1,null,2,3]

Output: [1,3,2]

Explanation:

Example 2:

Input: root = [1,2,3,4,5,null,8,null,null,6,7,9]

Output: [4,2,6,5,7,1,3,9,8]

Explanation:

Example 3:

Input: root = []

Output: []

Example 4:

Input: root = [1]

Output: [1]

 

Constraints:

• The number of nodes in the tree is in the range [0, 100].
• -100 <= Node.val <= 100

 

Follow up: Recursive solution is trivial, could you do it iteratively?
A:

用递归

/**

* Definition for a binary tree node.

* struct TreeNode {

* int val;

* TreeNode *left;

* TreeNode *right;

* TreeNode() : val(0), left(nullptr), right(nullptr) {}

* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}

* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}

* };

*/

class Solution {

public:

vector<int> inorderTraversal(TreeNode* root) {

vector<int> V;

helper(V, root);

return V;

}

private:

void helper(vector<int> &V, TreeNode* root){

if(root == nullptr){

return;

}

helper(V, root->left);

V.push_back(root->val);

helper(V, root->right);

}

};

---------------用stack迭代  ， ----------

----------每个节点pop出来的时候，才去visit， 入栈时走左边，出栈后，走右边
又是双100%

class Solution {

public:

vector<int> inorderTraversal(TreeNode* root) {

stack<TreeNode*> S; // push first, only use the value when pop

vector<int> V;

auto runner = root;

while (runner) {

S.push(runner);

runner = runner->left;

}

while (!S.empty()) {

auto tmp = S.top();

S.pop();

V.push_back(tmp->val);

runner = tmp->right;

while (runner) {

S.push(runner);

runner = runner->left;

}

}

return V;

}

};

--------下面是更早的一次解法， 思想类似，这是更简洁了-----------

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    vector<int> inorderTraversal(TreeNode* root) {
        vector<int> V;
        stack<TreeNode*> S;
        while(root || !S.empty()){
            if(root){
                S.push(root);
                root = root->left;
            }else{
                auto tmp = S.top();
                V.push_back(tmp->val);
                if(tmp->right)
                    root = tmp->right;
                S.pop();
            }
        }
        return V;
    }
};

Learned:
1：  in-order iterative traversal的关键点是两个：
       1）  把左节点先都加进去， 然后， 一个个地弄出来，visit + 考虑右子树
       2）  在循环的时候，并不是每次都pop，
       3） 通过curNode 是否为null来标记 当前我们是否走到了right节点的最下边，不是的话，就要重新考虑其左右子节点。 (或者说，标记是否刚刚走的是right 节点）