Leetcode 94.二叉树的中序遍历

题目

给定一个二叉树的根节点 root ，返回 它的中序 遍历 。

输入：root = [1,null,2,3]
输出：[1,3,2]

进阶: 递归算法很简单，你可以通过迭代算法完成吗？

递归遍历

递归遍历就是一个很简单的中序遍历

/**
 * 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:
    void istree(TreeNode* root,vector<int>& arr2)
    {
        if(root==nullptr)
        return;
        istree(root->left,arr2);//先遍历左子树

        arr2.push_back(root->val);//保存当前节点的值
        istree(root->right,arr2);//遍历右子树
        return;
    }
    vector<int> inorderTraversal(TreeNode* root) 
    {
        vector<int> arr1;
        istree(root,arr1);
        return arr1;
    }
};

进阶：利用栈来非递归迭代完成

/**
 * 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> arr1;
        stack<TreeNode*> st;//创建一个指针类型的栈
        TreeNode* cur=root;//cur保存根节点
        while(cur||!st.empty())//cur不为空，或者栈里还有节点指针就继续遍历
        {
            //先遍历保存所有左路节点并入栈
            while(cur)
            {
                st.push(cur);
                cur=cur->left;
            }

            //此时栈顶为最左节点，插入到arr1并pop掉
            TreeNode* top=st.top();
            st.pop();
            arr1.push_back(top->val);

            //访问左路节点的右子树
            cur=top->right;
            //右子树为空也不需要担心只要stack中还有节点下一次循环top就会捕获到并插入到arr1中

        }

        return arr1;
    }
};