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

For example:
Given binary tree [1,null,2,3],

   1
    \
     2
    /
   3

return [1,3,2].

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

树的中续遍历,要求使用循环完成。 基本思路为用Stack模拟recursion,先向左入栈到尽头,再逐层出栈,此时将结点值放入结果List中,如果出栈时遇到存在右结点,则先保存该节点并出栈,然后利用储存好的结点重复上述遍历。当栈清空时,循环终止。

 


class Solution {
public:
        stack<TreeNode*> treeStack;
    
        vector<int> inorderTraversal(TreeNode* root) 
        {
                vector<int> res;
                if(root)
                {
                        treeStack.push(root);
                        TreeNode* ptr = root;
                        while(!treeStack.empty())
                        {
                                while(ptr->left)
                                {
                                        ptr = ptr->left;
                                        treeStack.push(ptr);
                                }
                
                                ptr = treeStack.top();
                                treeStack.pop();
                                res.push_back(ptr->val);
                
                                while(!ptr->right)
                                {
                                        if(!treeStack.empty())
                                        {
                                                ptr = treeStack.top();
                                                treeStack.pop();
                                                res.push_back(ptr->val);
                                        }
                                        else
                                        {
                                                ptr = nullptr;
                                                break;
                                        }
                        }
                
                        if(ptr) 
                        {
                                ptr = ptr->right;
                                treeStack.push(ptr);
                        }
                  }
            }
        
            return res;
    }
};

Leave a Reply

Your email address will not be published. Required fields are marked *