首页 > 代码库 > 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; } };
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。