首页 > 代码库 > leetcode第一刷_Binary Tree Inorder Traversal

leetcode第一刷_Binary Tree Inorder Traversal

递归实现当然太简单,也用不着为了ac走这种捷径吧。。非递归实现还挺有意思的。

树的非递归遍历一定要借助栈,相当于把原来编译器做的事情显式的写出来。对于中序遍历,先要访问最左下的节点,一定是进入循环后,不断的往左下走,走到不能走为止,这时候,可以从栈中弹出访问的节点,相当于“左根右”过程的“根”,然后应该怎么做呢?想一下中序遍历完根节点之后应该干嘛,对,是走到右子树中继续重复这个过程,但是有一点,如果这个节点不包含右子树怎么办?这种情况下,下一个应该访问的节点应该是他的父亲,他的父亲现在应该就在栈顶,但是不要忘记每次进入循环的时候都是一直往左子树跑,所以要把当前节点置空,这样跳过走左子树的循环直接操作栈。

是不是比只写递归的收获多一些?

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