---

版权声明：本文为博主原创文章，转载请注明出处。
个人博客地址：https://yangyuanlin.club
欢迎来踩~~~~

---

题目

• 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?
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:

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

递归思想

思路

中序遍历的递归思想实现。顺序为：左 → 根 → 右。

代码

vector<int> inorderTraversal(TreeNode *root)
{
    // 二叉树中序遍历
    vector<int > v;
    if(root == NULL)return v;
    inorder_help(root, v);
    return v;
}
/*
* 中序遍历顺序：左 → 根 → 右。
*/
void inorder_help(TreeNode *root, vector<int > &v)
{
    if(!root)return;
    inorder_help(root->left, v);// 递归左子树
    v.push_back(root->val);// 保存根
    inorder_help(root->right, v);// 递归右子树
}

非递归思想

思路

用非递归模拟二叉树的中序遍历，思路是：优先遍历根节点的左孩子结点，放入一个栈中，遍历到底；然后从栈中取结点，栈的特点是后进先出，从最后的节点开始加入vector数组；接着遍历该结点的右孩子结点，把该孩子结点当作根节点遍历左孩子结点。
实现的思想和递归是一样的，就是根据中序遍历的特点，中序遍历顺序：左 → 根 → 右，即：

inorder(root -> left);// 左子树
get(root -> val);// 根
inorder(root -> right);// 右子树

代码

vector<int> inorderTraversal(TreeNode *root)
{
    vector<int > v;
    stack<TreeNode* > s;
    TreeNode *node = root;
    while(!s.empty() || node!=NULL)
    {
        // 以当前结点为根，顺着左子树找到底
        while(node != NULL)
        {
            s.push(node);
            node = node->left;
        }
        node = s.top();
        s.pop();
        v.push_back(node->val); // 左边遍历完了，保存根结点
        node = node->right; // 遍历右子树结点
    }
    return v;
}

以上。

---

版权声明：本文为博主原创文章，转载请注明出处。
个人博客地址：https://yangyuanlin.club
欢迎来踩~~~~

---