浅析二叉树的结构与遍历，递归和非递归的方式

如题所述

举报该问题

第1个回答 2024-09-04

今天来学习树的遍历，递归和非递归的方式

树的结构functionTreeNode(val,left,right){this.val=(val===undefined?0:val)this.left=(left===undefined?null:left)this.right=(right===undefined?null:right)}树的遍历

深度优先遍历DFS（递归）functionDFS(root){if(root===null)return;DFS(root.left);DFS(root.right);}深度优先遍历DFS（栈）

其实可以不用递归，小伙伴们可以在纸上画一画，等我有时间了再做几个图吧

functionDFS(root){conststack=[];stack.push(root);while(stack.length>0){root=stack.pop();if(root.right)stack.push(root.right);if(root.left)stack.push(root.left);}}广度优先遍历BFS（队列）functionBFS(root){constqueue=[];queue.unshift(root);while(queue.length>0){root=queue.pop();if(root.left)queue.unshift(root.left);if(root.right)queue.unshift(root.right);}}94.二叉树的中序遍历

中序遍历是先遍历左子树，然后访问根节点，然后遍历右子树。

左-中-右

https://leetcode-cn.com/problems/binary-tree-inorder-traversal/

144.二叉树的前序遍历

中-左-右

https://leetcode-cn.com/problems/binary-tree-preorder-traversal/

145.二叉树的后序遍历

左-右-中https://leetcode-cn.com/problems/binary-tree-postorder-traversal/

前序：根左右；中序：左根右；后序：左右根；中序常用来在二叉搜索数中得到递增的有序序列；后序可用于数学中的后缀表示法，结合栈处理表达式，每遇到一个操作符，就可以从栈中弹出栈顶的两个元素，计算并将结果返回到栈中；

【解法一】递归DFS

使用递归，三种遍历方式的书写方式比较统一

/***@param{TreeNode}root*@return{number[]}*/functioninorderTraversal(root){//定义一个结果数组，用来保存遍历的节点的值constresult=[];//定义递归函数functioninorder(root){//递归出口，直到节点为空，退出递归if(root===null)return;//【三种遍历方式更换顺序即可】//递归调用，传入根节点的左孩子inorder(root.left);//【中序遍历：左-中-右】//将根节点的值放入result数组中result.push(root.val);//递归调用，传入根节点的右孩子inorder(root.right);}//执行递归函数表示当前遍历到root节点的答案inorder(root);returnresult;}

【解法二】非递归迭代法-栈

非递归，用一个栈

中序遍历

用一个栈和循环来模拟递归操作

遍历这颗树和栈，用while循环

functioninorderTraversal(root){constresult=[]conststack=[]//遍历树，结束终点：节点为空且栈为空while(root||stack.length>0){//遍历root节点及其所有左孩子入栈while(root){stack.push(root)root=root.left}//左孩子遍历完入栈了，栈顶元素出栈【左-中】root=stack.pop()//中序【左-中-右】【左-中】result.push(root.val)//指向右孩子，没有就是null，下次循环就会出栈一个元素root=root.right}returnresult}

前序遍历varpreorderTraversal=function(root){constresult=[]conststack=[]while(root||stack.length>0){while(root){//【前序：中-左-右】result.push(root.val)stack.push(root)root=root.left}root=stack.pop()root=root.right}returnresult};

后序遍历（重难点）varpostorderTraversal=function(root){constresult=[]conststack=[]//用来标记节点letprev=nullwhile(root||stack.length>0){while(root){//遍历节点左孩子到底【左】stack.push(root)root=root.left}//栈顶出栈一个节点进行下面操作root=stack.pop()//【后序：左-右-中】//有右孩子，且右孩子没有被标记过，就将右孩子入栈，再while遍历右孩子if(root.right!==null&&root.right!==prev){//节点进栈，指针移向右孩子，再去循环【右】stack.push(root)root=root.right}else{//此时，没有右孩子【左-右-中】，或者有右孩子，但是被标记过了的【中】//将节点的值存入结果数组result.push(root.val)//存过的节点进行标记prev=root//节点清空root=null}}returnresult};

【解法三】Morris中序遍历

将二叉树转化为链表，即每一个node都只可能有右孩子

functioninorderTraversal(root){constresult=[];letpredecessor=null;while(root!==null){if(root.left){//predecessor节点就是当前root节点向左走一步，然后一直向右走至无法走为止predecessor=root.left;while(predecessor.right&&predecessor.right!==root){predecessor=predecessor.right;}//让predecessor的右指针指向root，继续遍历左子树if(!predecessor.right){predecessor.right=root;root=root.left;}else{//说明左子树已经访问完了，我们需要断开链接result.push(root.val);predecessor.right=null;root=root.right;}}else{//如果没有左孩子，则直接访问右孩子result.push(root.val);root=root.right;}}returnresult;}