Binary Tree Inorder Traversal

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

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

   1
    \
     2
    /
   3

return [1,3,2].

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

confused what "{1,#,2,3}" means? > read more on how binary tree is serialized on OJ.

OJ’s Binary Tree Serialization:The serialization of a binary tree follows a level order traversal, where ‘#’ signifies a path terminator where no node exists below.Here’s an example:

   1
  / \
 2   3
    /
   4
    \
     5

The above binary tree is serialized as "{1,2,3,#,#,4,#,#,5}".

Tags: TreeHash TableStack

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    vector<int> inorderTraversal(TreeNode* root) {
        vector<int> ans;
        stack<TreeNode *> s;
        TreeNode * curr = root;
        while(curr || !s.empty()){
            while(curr){
                s.push(curr);
                curr = curr->left;
            }
            curr = s.top();
            s.pop();
            ans.push_back(curr->val);
            curr = curr->right;
        }
        return ans;
    }
};

用循环代替递归，必然引进一个栈来模拟递归调用时存储的相关信息。

这里我用node的子节点是否全为空来标记该节点是否被已经被访问过– 第一次访问时按照-右节点-当前节点-左节点的顺序把节点压入栈中。并把当前节点的左右节点置空。

这样，程序便按照左节点-当前节点-右节点的顺序遍历了整个树结构，也即inorder traversal。

注意，该方法会修改原树的结构。

版本一：改变树的结构

/**
 * Definition for binary tree
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    stack<TreeNode *> s;
    vector<int> inorderTraversal(TreeNode *root) {
        vector<int> re;
        if(root == NULL){
            return re;
        }
        s.push(root);
        while(!s.empty()){
            TreeNode * p = s.top();
            s.pop();
            if(p->right != NULL){
                s.push(p->right);
            }
            if(p->right == NULL && p->left == NULL){
                re.push_back(p->val);
            }
            else{
                s.push(p);
            }
            if(p->left != NULL){
                s.push(p->left);
            }
            p->right = p->left = NULL; // WARNING: this will change the structure of original tree
        }
        return re;
    }
};

版本二：不改变树的结构

我们换一个角度来考虑inorder traversal的顺序：

1. 给定一个节点p，如果该节点有左节点，则把该节点压入栈中，移动p至左节点，重复此操作；

2. 此时，p没有左节点，把p的val压入结果数组中。

3. 如果p的右节点为空，则栈顶元素出栈，赋给p，把p的val压入结果数组。重复步骤3

4. 如果p的右节点非空，p=p->right，跳至步骤1.

/**
 * Definition for binary tree
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    stack<TreeNode *> s;
    vector<int> inorderTraversal(TreeNode *root) {
        vector<int> re;
        if(root == NULL){
            return re;
        }
        TreeNode * p = root;
        while(p != NULL || !s.empty()){
            if(p != NULL){
                while(p->left != NULL){
                    s.push(p);
                    p = p->left;
                }
                re.push_back(p->val);
                p = p->right;
            }
            else{//p is NULL
                p = s.top();
                s.pop();
                re.push_back(p->val);
                p = p->right;
            }
        }
        return re;
    }
};