Leetcode刷题记录--94. Binary Tree Inorder Traversal

做这一道题主要是为了回顾一下二叉树的中序遍历，其主要思路如下：

• 因为中序遍历需要先对左子树进行递归，因此在使用非递归方式的时候，也必须先处理左边的子树，因此对于一个节点，如果它存在左儿子，应当先把左儿子入栈。
• 当找到一个节点，这个节点不含有左儿子时，这意味着相对于这个节点而言，它已经没有需要处理的左子树了，就可以将其出栈，并将其打印出来。
• 这时候我们转而考虑该节点的右儿子，如果存在右儿子，入栈。
• 但是此时不能够将右儿子弹出打印，我们需要考虑以右儿子为根节点的情况，即它有没有左儿子，因此我们又回到了步骤一。

/**
 * 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) {
        TreeNode* p = root;
        TreeNode* temp;
        stack<TreeNode*> stack;
        vector<int> resultVec;

        while(p || !stack.empty()){

            while(p){
                stack.push(p);
                p = p->left;
            }
            
            if(!stack.empty()){
                p = stack.top();
                stack.pop();
        
                resultVec.push_back(p->val);
                p = p->right;
                
            }
            
                

                
        }
        return resultVec;
    }
};

Leetcode刷题记录--94. Binary Tree Inorder Traversal

原文：https://www.cnblogs.com/yuyuan-bb/p/12606570.html