树的非递归后序遍历,核心代码有给小白的注释 LeetCode145. Binary Tree Postorder Traversal


树的非递归遍历代码,我个人认为是很难自己想出来的,树实战听完许老师讲的思路可以说非常清楚了,想想自己刚进ACM的时候大神都是交流思路,亚洲区金奖、世界总决赛的大神们这些代码对他们来说都是Hello World,那时候我是一行一行学别人AC的代码。现在好多问题我也能一听思路就能写出代码,看见好多人上课的时候各种懵逼我就想起来我原来训练的时候。所以写了些注释供刚来的同学参考,本人是ACM水货一枚,不好的地方,欢迎大家指正。
大家要像许老师和林奔老师学习啊,有能力专注于思路,这是一个做好工程师基础能力。
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */

struct StackNode{
    TreeNode *root;
    bool isLeft;//用来判断当前是不是从左子树上来的
};

class Solution {
public:
    vector<int> postorderTraversal(TreeNode* root) {
        
        ans.clear();//清空缓存区是一种良好的习惯,和AC题目无关
        if (root == NULL){
            return ans;
        }
        
        Search(root);
        
        return ans;
    }
    
    void Search(TreeNode *root){
        stack<StackNode> st;
 
        while (!st.empty() || root != NULL){//栈不为空说明还有节点只入栈而没有访问,root不为NULL说明我当前要从
                                            //这个节点开始遍历,比如刚开始的时候从根节点开始遍历
            
            while (root != NULL){//有左子树的话,就一直找到最底的左子树
                StackNode node;
                node.root = root;
                node.isLeft = true;//标记,这是搜索左子树的过程
                st.push(node);
                root = root->left;
            }
            
            if (!st.empty()){//栈里没有节点,说明是空指针,也就是当前root为空,直接返回就好了
                StackNode node = st.top();
                st.pop();
                
                if (node.isLeft == true){//因为是后序遍历,要顺着左子树走下去,再上来从右子树找下去
                                         //从右子树上来我门才能访问根节点,在这里标记一下,入栈开始访问右子树。
                    node.isLeft = false;
                    st.push(node);
                    root = node.root->right;//这句话的意思是,我要从它的右子树开始搜索了。
                }else{
                    ans.push_back(node.root->val);//如果是从右子树扩展结束上来的节点,那我们就可以访问了。
                    root = NULL;
                }
            }
        }
    }
    
private:
    vector<int> ans;
};
已邀请:

要回复问题请先登录注册

返回顶部