序大家好，我是bigsai，好久不见，很想你们！今天就带大家攻克二叉树的前中后序遍历，包括递归和非递归方法，所学即所得！很多时候我们需要用非递归的方式来实现二叉树的遍历，非递归的枚举比递归的方式难度大一些，而且效率普遍更高，前中后后的难度序枚举是递增形式，非递归枚举有的人停在非递归后序，有的人停在非递归中序，有的人停在非递归前序（这个有点臀部，兄弟）。让我们回顾一下递归。它的底层其实就是维护一个栈，把数据存入栈中，每次把数据丢到栈顶进行处理（也就是递归、dfs的方向性、极端枚举特性非常明显）。我们在控制递归的时候，更重要的是把握上下层的逻辑关系。而不是递归的方法，除了掌握上下层的逻辑关系外，还得手动处理各种条件变化的细节。递归是一种单向过程。如果我们的逻辑只是在单程或回程中还好，有的时候你甚至要保持来来回回的状态，所以逻辑上还是比较吃力的。二叉树的前序遍历二叉树的前序遍历是最简单的，它的枚举方式是最简单的dfs。如果学习了二叉树的前序遍历，以后上手dfs就会容易很多。二叉树前序遍历的枚举规则是：根节点--->左子树--->右子树，即给定一棵树，输出当前节点，然后枚举左子树（左子树还是按照根的左右的顺序进行），最后枚举右子树（右子树也是按照根的左右的顺序进行），这样得到的一个枚举序列way是二叉树的前序遍历序列（也叫前序）。二叉树中前序遍历的顺序可以看下图（红色箭头指向需要访问的那个，可以看出会从父节点枚举第一次访问).在具体实现方法上，有递归和非递归两种方法。递归实现的二叉树的前序遍历非常简单。对于递归，我们只需要考虑初始情况、结束边界、中间法线点逻辑即可。初始情况：枚举从根节点开始，函数执行将根节点作为参数传递。结束边界：如果节点的左（或右）子节点为null，则停止相应节点的递归执行。普通点逻辑：先处理当前点（存储或输出），递归调用枚举左子树（如果不为空），递归调用枚举右子树（如果不为空）。你可以试试ac:classSolution{Listvalue=newArrayList();publicListpreorderTraversal(TreeNoderoot){qianxu(root);returnvalue;}privatevoidqianxu(TreeNodenode){if(node==null)return;value。add(node.val);qianxu(node.left);qianxu(node.right);}}非递归非递归的前序还是很简单的，前序遍历的规则是：根节点，左节点，右节点。但是根的左方向一直往下走，没有手工枚举的递归过程。我们往下怎么找对点呢？先用栈存储经过的节点，第一次枚举节点。在栈中，第二次是在抛出的时候枚举出正确的节点。它的规则大致是：一直访问当前节点并用栈来存储，节点指向左节点，直到左孩子为null。不会访问抛出堆栈的顶部。如果有右节点，访问其右节点并重复步骤1，如果没有右节点，则继续重复步骤2并抛出。这样的逻辑会从根开始，先访问左边，访问根和左边后，再访问右边的节点（子树），得到一个完整的前序遍历序列。具体实现代码为：classSolution{publicListpreorderTraversal(TreeNoderoot){Listvalue=newArrayList();Stackq1=newStack();while(!q1.isEmpty()||root!=null){while(root!=null){value.add(root.val);q1.push(root);root=root.left;}root=q1.pop();//抛出root=root。right;//准备访问它的右节点}returnvalue;}}二叉树的中序遍历二叉树的中序遍历频率是相当高的。如果是二叉排序树，问题还蛮多的，要知道二叉排序树的中序遍历是一个有序序列。如果你正在寻找二叉排序树的topk问题，非递归中序是非常有效的。二叉树中中序遍历的顺序如下图所示（红色箭头指向需要访问的那个，可以看出如果子树为null，则必须访问，否则它只会在从左子树返回时访问这个节点）。递归法递归法实现起来非常简单，其逻辑类似于先序递归。里口94只是有二叉树中序遍历。这里我直接放了代码：){if(root==null)return;zhongxu(root.left,value);value.add(root.val);zhongxu(root.right,value);}}非递归非递归中序和前序很相似，前序遍历的规则是：根节点，左节点，右节点。中序遍历的顺序是左节点、根节点、右节点。前序中，先根后左，其实是一种有些重叠的关系（左为下一个跟）。在它的非递归枚举实现中，我们访问右节点的时候是先不访问就抛出父节点，直接访问父节点的右节点。如果抛出父节点去访问父节点，其实就是中序节点。它的规则大致是：枚举当前节点（不存储输出）用栈存储，节点指向左节点，直到左孩子为null。抛出栈顶访问。如果有右节点，访问其右节点并重复步骤1，如果没有右节点，则继续重复步骤2并抛出。这样的逻辑会形成一个中序序列，因为叶子节点的左右为null，这样的规则还是满足中序的。实现代码为：classSolution{publicListinorderTraversal(TreeNoderoot){Listvalue=newArrayList();Stackq1=newStack();while(!q1.isEmpty()||root!=null){while(root!=null){q1.push(root);root=root.left;}root=q1.pop();//throwvalue.add(root.val);root=root.right;//准备访问它的右节点}returnvalue;}}二叉树的后序遍历二叉树的后序遍历非递归方式是最难实现的。能手写非递归后序，绝对让面试官眼前一亮！二叉树中后序遍历的顺序可以看下图（红色箭头指向需要访问的，可以看出如果子树为null，则必须访问，否则仅当从右子树返回时才访问该节点）。递归二叉树递归后序遍历非常简单。跟pre-order和in-order的逻辑是一样的。大家可以在里口145试试后序的代码测试，下面是我直接写的后序递归方法：);returnvalue;}privatevoidhouxu(TreeNoderoot){if(root==null)return;houxu(root.left);houxu(root.right);//右子树返回value.add(root.val);}}非递归非递归后序有点难，大家可以回头看看二叉树的前序和中序遍历。其实直接扔一个栈就可以找到正确的节点。抛出之后，栈就会为空，但是这次后序遍历的顺序是左子树-->右子树--->根节点，也就是处理完右节点后，还得回头访问的根节点。因此，逻辑结构与先序和中序的非递归实现略有不同。Preorder，中序遍历的顺序提取为：Preorder：middlepush—>leftpush—>leftchild进出—>leftstack—>middlepop—>rightpush—>rightchild进出—>right出栈前遍历同一个大进程，按照出栈顺序形成一个前序序列。中序：中推—>左推—>左孩子进出—>左入栈—>中推—>右推—>右孩子进出—>右出栈，中序遍历同大按照堆叠顺序加工成有序序列，但后序需要考虑什么？其实准备从左孩子pop到中间的时候，先不要出栈记录为第一次，然后再入栈。如果是从右孩子返回，那么这个结点就是第三次遍历（第一次访问，然后枚举左边返回第二次，枚举右边返回第二次），此时抛出形成后序。不懂的话，这里有一张简单的图帮助大家理解：idea理解了，怎么实现呢？最简单的方法是使用哈希图来存储节点访问次数。附上个人实现代码：classSolution{publicListpostorderTraversal(TreeNoderoot){Listvalue=newArrayList();Stackq1=newStack();Mapmap=newHashMap<>();while(!q1.isEmpty()||root!=null){if(root!=null){q1.push(root);map.put(root,1);//t.value标记这个值节点出现次数root=root.left;}else{root=q1.peek();if(map.get(root)==2){//第二次访问，抛出q1.pop();value.add(root.val);root=null;//需要上去}else{map.put(root,2);root=root.right;}}}returnvalue;}}但是如果面试官问Whatshould如果你有哈希冲突，你会怎么做？虽然这个概率很小，几乎不可能，面试官不会放过你，但是你还是需要用正统的方法来实现。那么正统的方法怎么解决呢？这也很容易。使用一个前节点来保持最后抛出访问的点。如果当前抛出的右孩子为pre或者当前节点的右节点为null，则抛出该点。不然就“重建”一次！实现代码为：classSolution{publicListpostorderTraversal(TreeNoderoot){TreeNodetemp=root;//枚举临时节点Listvalue=newArrayList<>();TreeNodepre=null;//前置节点Stack堆栈=新堆栈<>（）；while(!stack.isEmpty()||temp!=null){while(temp!=null){stack.push(temp);temp=temp.left;}temp=stack.pop();if(temp.right==pre||temp.right==null)//需要弹出{value.add(temp.val);pre=temp;temp=null;//需要重新从栈中抛出}else{stack.push(temp);temp=temp.right;}}returnvalue;}}是不是觉得很巧妙？那再说说另一种show操作的代码，看看左、右、中，依次是中、右、左。这不是逆序遍历吗！所以进行反向前序遍历，然后翻转结果得到这个值。当然，你同时使用双栈翻转也是如此！实现代码为：classSolution{publicListpostorderTraversal(TreeNoderoot){Listvalue=newArrayList();Stackq1=newStack();while(!q1.isEmpty()||root!=null){while(root!=null){value.add(root.val);q1.push(root);root=root.right;}root=q1.pop();//抛出root=root.left;//准备访问其右节点}Collections.reverse(value);//将结果取反其中一个序列必须包含中序遍历序列的前序，中序决定二叉树和后序，同理，中序决定一棵二叉树。前序和中序确定一棵二叉树根据一棵树的前序遍历和中序遍历构造一棵二叉树。当然也是力途105的原题。注：可以假设树中没有重复元素。分析：给定一个前序序列和一个中序序列，并且其中没有重复的元素，如何构造一棵二叉树？我们可以先分别观察两个序列的特点：前序遍历：遍历规则为（root,[leftarea],[rightarea]）。中序遍历：遍历规则为([leftregion],root,[rightregion])。前序遍历的左边区域和中序遍历的左边区域包含的元素范围相同，根也相同。所以可以这样做：根据前序遍历中的第一个找到根节点，就可以确定根了。通过中序遍历找到根节点的值，这样就可以知道左区和右区的节点个数。根节点的左区域由前中序序列确定的左区域确定，根节点的右节点由前中序序列的右区域确定。一些操作可以借助这张图来理解：在具体实现中，可以使用HashMap来存储有序的存储序列，避免重复计算。实现的代码是：/***Definitionforabinarytreenode.*publicclassTreeNode{*intval;*TreeNodeleft;*TreeNoderight;*TreeNode(intx){val=x;}*}*/classSolution{publicTreeNodebuildTree(int[]preorder,int[]inorder){if(preorder.length==0)returnnull;TreeNoderoot=newTreeNode(preorder[0]);Mapmap=newHashMap();for(inti=0;imap,intinStart,intinEnd){//TODOAuto-generatedmethodstubif(preEndmap=newHashMap();for(inti=0;imap,intinStart,intinEnd){//TODOAuto-generatedmethodstubif(postEnd
