php做网站安全,人力资源网,内蒙古seo公司,怎样在本机建设网站说在前面 #x1f388;二叉树大家应该都很熟了吧#xff0c;那二叉树的这五种遍历方式你们都会了吗#xff1f; 以这一二叉树为例子#xff0c;我们来看看不同遍历方式返回的结果都是怎样的。
前序遍历
前序遍历的顺序是#xff1a;首先访问根节点#xff0c;然后递归地…说在前面 二叉树大家应该都很熟了吧那二叉树的这五种遍历方式你们都会了吗 以这一二叉树为例子我们来看看不同遍历方式返回的结果都是怎样的。
前序遍历
前序遍历的顺序是首先访问根节点然后递归地遍历左子树最后递归地遍历右子树。
var preorderTraversal function(root) {const res [];const traversal (r){if (r null) return;res.push(r.val); // 访问根节点traversal(r.left); // 遍历左子树traversal(r.right); // 遍历右子树};traversal(root);return res;
};输出结果
[3,9,20,15,7]中序遍历
中序遍历的顺序是首先递归地遍历左子树然后访问根节点最后递归地遍历右子树。
var inorderTraversal function(root) {const res [];const traversal (r){if (r null) return;traversal(r.left); // 遍历左子树res.push(r.val); // 访问根节点traversal(r.right); // 遍历右子树};traversal(root);return res;
};输出结果
[9,3,15,20,7]后序遍历
后序遍历的顺序是首先递归地遍历左子树然后递归地遍历右子树最后访问根节点。
var postorderTraversal function(root) {const res [];const traversal (r){if (r null) return;traversal(r.left); // 遍历左子树traversal(r.right); // 遍历右子树res.push(r.val); // 访问根节点};traversal(root);return res;
};输出结果
[9,15,7,20,3]层序遍历
层序遍历按照从上到下、从左到右的顺序访问二叉树的所有节点。
以广度优先策略遍历节点的方法
使用队列作为辅助数据结构。按照节点的深度层次访问二叉树从根节点开始逐层向下。
var levelOrderTraversal function(root) {const res [];const queue [root];if(!root) return [];while(queue.length 0){const node queue.shift();res.push(node.val);node.left queue.push(node.left);node.right queue.push(node.right);}return res;
};输出结果
[3,9,20,15,7]垂序遍历
对位于 (row, col) 的每个结点而言其左右子结点分别位于 (row 1, col - 1) 和 (row 1, col 1) 。树的根结点位于 (0, 0) 。 二叉树的 垂序遍历 从最左边的列开始直到最右边的列结束按列索引每一列上的所有结点形成一个按出现位置从上到下排序的有序列表。如果同行同列上有多个结点则按结点的值从小到大进行排序。
在层序遍历的基础上记录每个数据所在的位置再重新进行排序即可。
var verticalTraversal function (root) {const nodeList [];const q [{ node: root, row: 0, col: 0 }];//获取二叉树节点集合while (q.length) {const { node, row, col } q.shift();nodeList.push({ val: node.val, row: row, col });if (node.left) q.push({ node: node.left, row: row - 1, col: col 1 });if (node.right) q.push({ node: node.right, row: row 1, col: col 1 });}//对二叉树节点进行排序nodeList.sort((a, b) {if (a.row b.row a.col b.col) {return a.val - b.val;}return a.row - b.row;});//对二叉树节点进行分组const res [[nodeList[0].val]];for (let i 1; i nodeList.length; i) {if (nodeList[i].row ! nodeList[i - 1].row) {res.push([]);}res[res.length - 1].push(nodeList[i].val);}return res;
};输出结果
[[9],[3,15],[20],[7]]公众号
关注公众号『前端也能这么有趣』获取更多有趣内容。
说在后面 这里是 JYeontu现在是一名前端工程师有空会刷刷算法题平时喜欢打羽毛球 平时也喜欢写些东西既为自己记录 也希望可以对大家有那么一丢丢的帮助写的不好望多多谅解 写错的地方望指出定会认真改进 偶尔也会在自己的公众号『前端也能这么有趣』发一些比较有趣的文章有兴趣的也可以关注下。在此谢谢大家的支持我们下文再见 。
