LeetCode 94. Binary Tree Inorder Traversal,中序遍历树的代码带有详细注释


题目是让我们用迭代(for循环)实现树的中序遍历,众所周知,树的遍历递归核心代码只有三行,理解了写出来是在是so easy。但是迭代版本的遍历代码,还是比较难想的,但我们可以通过以下方式理解现有代码。

考虑我们手动是如何中序遍历一棵树的:
  • 从根节点开始,有左子树就一直顺着左子树找下去,直到没有左子树,访问该节点,然后看看有没有右子树,有德华就重复上面的过程,没有的话就返回到上一个没访问的子树根节点。
  • 然后就看代码怎么模拟这个过程,关键的步骤我都写了注释

class Solution {
public:
    vector<int> inorderTraversal(TreeNode* root) {
        ans.clear();
        if (root == NULL){
            return ans;
        }
        Search(root);
        return ans;
        
    }
    
    void Search(TreeNode *root){
        stack<TreeNode *> st;
        while ( !st.empty() || root != NULL){//只要还有没访问的节点,就一直进行下去
            
            while (root != NULL){//把当前节点入栈,然后有左子树就顺着左子树找下去。
                st.push(root);
                root = root->left;
            }
            
            if ( !st.empty() )
                root = st.top();{//沿着左子树找到最底了,就该访问最底的节点了。
                ans.push_back(root->val);
                st.pop();
                root = root->right;//访问完节点后,进入右子树进入相同的流程。
            }
        }
    }
    
    vector<int> ans;
};

1 个评论

发帖之前 先搜一下社区上有没有已有的题,如果已有那题,便可以回复在已有的那题之下哦:https://ask.julyedu.com/question/7244

要回复文章请先登录注册

返回顶部