网站集约化建设情况的汇报,做网站为什么要买网站空间,禅城教育网站建站,宿迁网站建设托管大家好#xff0c;又和大家见面啦#xff01;今天我们一起去看一下二叉树的前序中序后序的遍历#xff0c;相信这个对大家来说是信手拈来#xff0c;但是#xff0c;今天我们并不是使用常见的递归方式来解题#xff0c;我们采用迭代方式解答。我们先看第一道前序遍历
1…大家好又和大家见面啦今天我们一起去看一下二叉树的前序中序后序的遍历相信这个对大家来说是信手拈来但是今天我们并不是使用常见的递归方式来解题我们采用迭代方式解答。我们先看第一道前序遍历
1、前序遍历
二叉树的前序遍历 前序遍历是先将二叉树的根节点遍历再遍历左子树、右子树。我们做这道题的思想是把二叉树划分为两部分一是左路节点二是左路节点的右子树。什么是左路节点如上图的二叉树来说 这就算以8为根节点的二叉树的左路节点也就是以8为根节点它的左孩子的左孩子的左孩子......这一条路径。我们先让左路节点入栈因为是前序遍历所以我们入栈的同时遍历当前结点的val当左路结点都入栈完那么当前节点一定是没有左子树的我们让这个结点出栈这个时候我们处理当前结点的右子树右子树同样进行先让左路节点入栈.....循环做此操作直到右子树也会空然后将这个结点的所有左右子树我们都访问完成我们已经pop掉这个时候只需要处理新的栈顶元素就可以啦。
话不多说思路就是这个样子下面把代码写出来让大家看看。
定义一个cur从根节点开始然后定义一个栈存储左路结点一个vector存储左路节点的数据。
vectorint preorderTraversal(TreeNode* root) {stackTreeNode* st;vectorint v;TreeNode* curroot;//cur从根节点开始while(cur){while(cur){v.push_back(cur-val);st.push(cur);//左路结点入栈curcur-left;}//处理栈内的右子树TreeNode* topst.top();st.pop();curtop-right;//处理左路节点的右子树}return v;}
代码写起来很简单但是我们会发现这个提交是过不了的为什么呢大家看我们在把1的右节点赋给cur去处理1的右子树时结点1是没有右结点的这个时候cur为空上面这个大循环就进不去而这个时候我们其它的左路节点都还在栈里面没有处理所以外面这个大循环的判断条件是不正确的。应该改成
while(cur||!st.empty())
当栈不为空的时候我们也要处理。 然后我们再运行就可以通过了。
2、中序遍历
二叉树的中序遍历 我们还是拿这棵树来看其实中序和前序思路是完全一样只不过前序的遍历顺序是根左右我们左路结点入栈的时候就可以直接访问其val但是中序遍历的顺序是左根右所以我们写中序的时候应该把访问val的顺序调到结点出栈的时候访问就可啦。
下面我们开始实现
vectorint inorderTraversal(TreeNode* root) {stackTreeNode* st;vectorint v;TreeNode* curroot;while(cur||!st.empty()){while(cur)//左路结点进栈{st.push(cur);curcur-left;}TreeNode* topst.top();v.push_back(top-val);st.pop();curtop-right;//处理当前结点的右子树}return v;}
3、后序遍历
二叉树的后序遍历 后序遍历的遍历顺序是左右根我们只有把左右结点全部访问完成才能访问根节点的数据或者左右节点为空才能直接访问根节点的数据。左节点我们在左路子树入栈的时候就算是访问但是右节点怎么解决呢
所以说我们这里需要解决一下怎么才能知道右节点已经访问过了。我们以这里的结点6为例要访问结点6的val,首先我们把831入栈结点1没有右子树可以直接获取它的val,出栈后栈顶元素是33有右子树需要先处理它的右树然后64入栈这时栈顶结点为44没有右树直接获取它的val此时栈顶元素为66他有右树需要先处理他的右树此时结点7入栈这个时候7没有右树直接获取它的val这个时候结点6的左右树都访问完毕可以访问6的val了但是我们怎么判断结点6的左右树都已经访问完毕了呢结点6上一次访问的结点是7我们只需要判断6结点的上一次访问的结点是不是7就可以了。
我们可以定义一个结点prev,每访问完一个栈顶元素我们就把top赋给prev表示上一个访问结点我们只需要判断top-rightprev即我们已经访问过top-right这个结点就行了这样我们可以直接获取栈顶的val值。
因此只有在当前结点的右树为空或者当前结点的右结点是我们上一次访问的结点我们就可以获取它的val值。
下面我们开始写代码
vectorint postorderTraversal(TreeNode* root) {stackTreeNode* st;vectorint v;TreeNode* curroot;TreeNode* prevnullptr;while(cur||!st.empty()){while(cur){st.push(cur);curcur-left;}TreeNode* topst.top();//分情况讨论如果当前这个结点的右子树为空或者当前结点的右子树是我们上次访问的结点表示我们已经访问过它的子树就可以直接获取当前结点的valif(top-rightnullptr||top-rightprev){st.pop();v.push_back(top-val);prevtop;}//否者访问这个结点的右树else{curtop-right;}}return v;
到这里二叉树的前序中序后序三个非递归方式就讲解完毕啦。我们下次再见呀
