JavaScript算法 — 二叉树遍历
创始人
2024-01-20 16:16:35
0

目录

  • 1、构造二叉树
  • 2、递归遍历
  • 3、非递归遍历
    • 3.1 先序
    • 3.2 中序
    • 3.3 后序

1、构造二叉树

树节点:

// 二叉树节点的构造函数
function TreeNode(val, left, right) {this.val = (val===undefined ? 0 : val)this.left = (left===undefined ? null : left)this.right = (right===undefined ? null : right)
}

下面我们需要遍历下面这颗二叉树:
在这里插入图片描述
遍历结果:
先序:“中 - 左 - 右” 0137849256
中序:“左 - 中 - 右” 7381940526
后序:“左 - 右 - 中” 7839415620

2、递归遍历

调用递归的位置不同,结果分为三种。

var preorder = []// 前序结果
var inorder = []// 中序结果
var postorder = []// 后序结果var loop = function(root){// 当前节点为空,表示达到了叶子节点if (root == null) returnpreorder.push(root.val)  // 前序loop(root.left)inorder.push(root.val)// 中序loop(root.right)postorder.push(root.val)// 后序
}
loop(root)

3、非递归遍历

3.1 先序

  1. 根节点入栈,依此取出栈顶元素。
  2. 访问栈顶元素,同时出栈,将栈顶元素作为当前元素,当前元素右节点入栈,左节点入栈(注意:右先入那么右后出)。
  3. 重复上述操作,直到整个栈为空时,则遍历结束。
var preorderTraversal = function(root) {var arr = []arr.push(root)var res = []while (arr.length) {var temp = arr.pop()if (!temp) break;//当前节点的值放入结果数组res.push(temp.val)//右子树入栈if (temp.right) {arr.push(temp.right)}//左子树入栈if (temp.left) {arr.push(temp.left)}}return res
};

3.2 中序

  1. 循环将根节点和其的左子树入栈。
  2. 直到左子树为空时,访问栈顶元素,同时将栈顶元素作为当前元素,并出栈。
  3. 开始访问右子树,循环出栈直到整个栈为空时,则遍历结束。
var inorderTraversal = function(root) {var res = []var arr = []while(arr.length || root) {if (root) {arr.push(root)root = root.left} else {let temp = arr.pop()res.push(temp.val)root = temp.right}}return res
};

3.3 后序

和前序遍历思想相反。
先序是使用push往res数组后面加数据,二后序是使用unshift往数组前面加数据。

var postorderTraversal = function(root) {var arr = []arr.push(root)var res = []while(arr.length) {var temp = arr.pop()if (!temp) breakres.unshift(temp.val)// 从前往后塞入数据if(temp.left) {// 左节点先入栈arr.push(temp.left)}if(temp.right) {arr.push(temp.right)}}return res
};

相关内容

热门资讯

喜欢穿一身黑的男生性格(喜欢穿... 今天百科达人给各位分享喜欢穿一身黑的男生性格的知识,其中也会对喜欢穿一身黑衣服的男人人好相处吗进行解...
发春是什么意思(思春和发春是什... 本篇文章极速百科给大家谈谈发春是什么意思,以及思春和发春是什么意思对应的知识点,希望对各位有所帮助,...
网络用语zl是什么意思(zl是... 今天给各位分享网络用语zl是什么意思的知识,其中也会对zl是啥意思是什么网络用语进行解释,如果能碰巧...
为什么酷狗音乐自己唱的歌不能下... 本篇文章极速百科小编给大家谈谈为什么酷狗音乐自己唱的歌不能下载到本地?,以及为什么酷狗下载的歌曲不是...
华为下载未安装的文件去哪找(华... 今天百科达人给各位分享华为下载未安装的文件去哪找的知识,其中也会对华为下载未安装的文件去哪找到进行解...
怎么往应用助手里添加应用(应用... 今天百科达人给各位分享怎么往应用助手里添加应用的知识,其中也会对应用助手怎么添加微信进行解释,如果能...
家里可以做假山养金鱼吗(假山能... 今天百科达人给各位分享家里可以做假山养金鱼吗的知识,其中也会对假山能放鱼缸里吗进行解释,如果能碰巧解...
一帆风顺二龙腾飞三阳开泰祝福语... 本篇文章极速百科给大家谈谈一帆风顺二龙腾飞三阳开泰祝福语,以及一帆风顺二龙腾飞三阳开泰祝福语结婚对应...
美团联名卡审核成功待激活(美团... 今天百科达人给各位分享美团联名卡审核成功待激活的知识,其中也会对美团联名卡审核未通过进行解释,如果能...
四分五裂是什么生肖什么动物(四... 本篇文章极速百科小编给大家谈谈四分五裂是什么生肖什么动物,以及四分五裂打一生肖是什么对应的知识点,希...