二叉树的迭代法

本文主要是介绍二叉树的迭代法，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

简介

本篇文章介绍二叉树的前序，中序和后序遍历方法，并总结其框架。

前序遍历

前序遍历的顺序是：根节点->左子树->右子树。

迭代代码的思路为：

1.访问跟节点的同时，将右子树压入栈S。令下一个节点为左子树，直到遍历完所有的左子树。将S栈顶弹出，弹出的即为最近访问的右子树。

2.不断循环过程1，直到栈为空。

代码框架

栈S;
p= root;
while(p || S不空){    //栈S为空时退出循环，但是要排除第一次入栈的情况while(p){        //遍历P以及P的左节点，直到其为空访问p节点；p的右子树入S;  //注意：将右子树压入栈的顺序在它走向左子树之前。p = p的左子树;}p = S栈顶弹出;
}

详细代码

vector<int> preorderTraversal(TreeNode* root) {stack<TreeNode*> S;vector<int> v;TreeNode* rt = root;while(rt || S.size()){while(rt){S.push(rt->right);v.push_back(rt->val);rt=rt->left;}rt=S.top();S.pop();}return v;        }

后序遍历

后序遍历的顺序时：左子树->右子树->根节点。

这里采用逆序的遍历顺序，即根节点->右子树->左子树。因为遍历顺序正好相反，结果的顺序也会颠倒。

将最后得到的结果逆序即为正确答案。

代码框架

栈S;
p= root;
while(p || S不空){while(p){访问p节点；p的左子树入S;p = p的右子树;}p = S栈顶弹出;
}
结果序列逆序;

详细代码

vector<int> postorderTraversal(TreeNode* root) {stack<TreeNode*> S;vector<int> v;TreeNode* rt = root;while(rt || S.size()){while(rt){S.push(rt->left);v.push_back(rt->val);rt=rt->right;}rt=S.top();S.pop();}reverse(v.begin(),v.end());return v;}

中序遍历

中序遍历的顺序为：左子树->根节点->右子树

因此对于根节点，我们的第一反应是将其压入栈S，并不断遍历其左子树，直到左子树为空。当左子树遍历完之后，S栈顶即为最近的根节点。访问这个根节点后，接下来访问右子树。

代码框架

栈S;
p= root;
while(p || S不空){     //当S为空时，代表着所有的根节点都访问完while(p){         //当遍历完所有左子树时退出循环p入S;p = p的左子树;}p = S.top 出栈;访问p;p = p的右子树;
}

详细代码

 vector<int> inorderTraversal(TreeNode* root) {stack<TreeNode*> S;vector<int> v;TreeNode* rt = root;while(rt || S.size()){while(rt){S.push(rt);rt=rt->left;}rt=S.top();S.pop();v.push_back(rt->val);rt=rt->right;}return v;        }

总结

无论是前序，后序还是中序遍历都可以把代码归纳如下。

代码框架总结

栈S;
p= root;
while(p || S不空){while(p){//是否访问根节点？//是否将根节点/右子树压入栈p = p的左子树;}
p = S.top ;
S.pop();
//是否访问根节点/右子树？
}

迭代的思路弯弯绕绕，没有递归算法容易理解。但是仍然有规律可循，在第二个内部while循环中，总是要遍历左子树。左子树遍历完之后，将栈中的节点弹出。

特别之处在于，在先序遍历里的第二个内部while循环中，先访问根节点，并将右子树压入栈。内部while循环退出以后，栈顶元素时右子树。（后序遍历依次类推）

中序遍历的第二个内部while循环中，是将根节点压入栈。内部while循环退出以后，栈顶元素时根节点。因此得到根节点之后，便是访问根节点，再遍历其右子树。

参考资料

jason-2  二叉树的中序遍历 - 迭代法  力扣（LeetCode）

这篇关于二叉树的迭代法的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---