-
• 二叉树 VS 多叉树
-
• 二叉树
-
• 多叉树
-
• 二叉树遍历
-
• 二叉树的前序遍历
-
• 二叉树的中序遍历
-
• 二叉树的后序遍历
-
• 其他算法题
-
• 二叉树的最小深度
-
• 二叉树的最大深度
-
• 翻转二叉树
-
• 相同的树
二叉树 VS 多叉树
二叉树
二叉树(Binary Tree)是一种数据结构,它是由n(n≥0)个节点构成的有限集合。
这个集合或者为空集(即没有任何节点,称为空二叉树),或者由一个根节点以及两个互不相交的子集组成,这两个子集分别称为 左子树(left subtree) 和 右子树(right subtree),每个子集本身也是一棵二叉树。
具体来说:
-
1. 根节点:每棵非空二叉树都有且仅有一个被称为“根”的节点。
-
2. 子节点:每个节点最多可以有两个子节点,一个是左子节点,另一个是右子节点。
-
3. 递归定义:若一棵非空二叉树的根节点存在,则其左子树和右子树都是根据相同规则构造的二叉树。
举例说明:
5
/
3 7
/
2 4 8
上图展示了一棵非空二叉树,其中:
- 节点5是根节点。
- 节点3和节点7分别是节点5的左子节点和右子节点,它们各自又构成了两棵新的二叉树。
- 节点2和节点4是节点3的左、右子节点。
- 节点8是节点7的右子节点,而节点7没有左子节点。
按照二叉树的性质,任意节点的所有后代节点间都不会有交叉关系,即它们要么属于当前节点的左子树,要么属于右子树,不会同时出现在另一侧的子树中。
二叉树例子
const tree = {
val:'1',
left:{
val:'2',
left:{val:'4',left:null,right:null},
right:{val:'5',left:null,right:null}
},
right:{
val:'3',
left:{val:'6',left:null,right:null},
right:{val:'7',left:null,right:null}
}
}
多叉树
多叉树(Multiway Tree),又称多分支树或多路树,是一种更为通用的数据结构,每个节点可以有任意数量的子节点。
与二叉树不同,在多叉树中,每个节点可以有超过两个孩子的节点。
具体来说:
-
1. 根节点:每棵非空多叉树都有一个被称为“根”的节点。
-
2. 子节点:每个节点可以有多个子节点,这些子节点之间没有顺序上的优先级,通常以列表或其他集合形式存储。
举例说明:
A
/ |
B C D
/
E F G
/
H I
在上图所示的多叉树中:
- 节点A是根节点。
- 节点A有三个子节点B、C和D。
- 节点B有两个子节点E和F。
- 节点C没有子节点。
- 节点D有一个子节点G,而节点G又有两个子节点H和I。
多叉树在很多实际应用中出现,比如文件系统目录结构(一个目录下可以有多个子目录和文件)、组织架构(一个部门下可以有多个子部门或员工)等场景。
二叉树遍历
二叉树的前序遍历
二叉树的前序遍历,也叫根-左-右(Root-Left-Right)遍历,是一种常见的深度优先遍历方式。
它的遍历顺序是 首先访问根节点,然后遍历左子树,最后遍历右子树。
具体算法步骤如下:
-
1. 访问根节点。
-
2. 递归地对左子树进行前序遍历。
-
3. 递归地对右子树进行前序遍历。
例如,对于一个二叉树:
A
/
B C
/
D E F
其前序遍历结果为:A -> B -> D -> E -> C -> F
算法题
-
1. 二叉树的前序遍历
leetcode地址: https://leetcode.cn/problems/binary-tree-preorder-traversal/description/
给你二叉树的根节点 root ,返回它节点值的 前序 遍历。
示例 1:

输入:root = [1,null,2,3]
输出:[1,2,3]
示例 2:
输入:root = []
输出:[]
示例 3:
输入:root = [1]
输出:[1]
示例 4:

输入:root = [1,2]
输出:[1,2]
示例 5:

输入:root = [1,null,2]
输出:[1,2]
提示:
树中节点数目在范围 [0, 100] 内
-100 <= Node.val <= 100
进阶:递归算法很简单,你可以通过迭代算法完成吗?
js实现方案 — 使用递归
/**
* Definition for a binary tree node.
* function TreeNode(val, left, right) {
* this.val = (val===undefined ? 0 : val)
* this.left = (left===undefined ? null : left)
* this.right = (right===undefined ? null : right)
* }
*/
/**
* @param {TreeNode} root
* @return {number[]}
*/
var preorderTraversal = function (root) {
// 定义一个数组
let arr = []
// 定义需要递归的函数
var fun = (node) => {
// 如果节点存在
if (node) {
// 根节点
arr.push(node.val)
// 左子树
fun(node.left)
//右子树
fun(node.right)
}
}
fun(root)
return arr
};
js实现方案 — 使用栈方式
/**
* Definition for a binary tree node.
* function TreeNode(val, left, right) {
* this.val = (val===undefined ? 0 : val)
* this.left = (left===undefined ? null : left)
* this.right = (right===undefined ? null : right)
* }
*/
/**
* @param {TreeNode} root
* @return {number[]}
*/
var preorderTraversal = function (root) {
// 判断根节点
if (!root) return []
// 新建一个数组
let arr = []
// 根节点入栈
let stack = [root]
while (stack.length) {
// 出栈
let o = stack.pop()
arr.push(o.val)
// push 是往后加,所以,先加右侧
// {{左},左},{左},{左},{右},{右},{右},{右},{右} }
// pop 的时候,右侧先出
o.right && stack.push(o.right)
o.left && stack.push(o.left)
}
return arr
};
二叉树的中序遍历
二叉树的中序遍历是指按照“ 左子树-根节点-右子树 ”的顺序遍历二叉树的节点。
具体算法步骤如下:
中序遍历是二叉树遍历的一种方式,其步骤如下:
-
1. 先递归遍历左子树。
-
2. 访问根节点。
-
3. 递归遍历右子树。
如果以节点的值作为输出,中序遍历可以用递归或者迭代的方式实现。
假设有一个二叉树如下所示:
1
/
2 3
/
4 5
按照中序遍历的顺序输出结果为:[4, 2, 5, 1, 3]。
例子
在JavaScript中,二叉树的中序遍历同样可以通过递归或迭代方式实现。
以下是两种方法的代码示例:
递归实现
// 定义一个二叉树节点类
class TreeNode {
constructor(val, left = null, right = null) {
this.val = (val === undefined ? 0 : val);
this.left = left;
this.right = right;
}
}
// 中序遍历(递归)
function inorderTraversal(root) {
if (!root) return []; // 如果根节点为空,则返回空数组
return [
...inorderTraversal(root.left), // 首先遍历左子树
root.val, // 然后访问根节点
...inorderTraversal(root.right) // 最后遍历右子树
];
}
迭代实现
function inorderTraversal(root) {
let result = [];
let stack = [];
while (root || stack.length > 0) {
while (root) { // 将所有左孩子压入栈,并将当前节点移到其右孩子
stack.push(root);
root = root.left;
}
// 弹出栈顶元素并访问节点
root = stack.pop();
result.push(root.val);
// 移动到当前节点的右孩子
root = root.right;
}
return result;
}
以上两种方法都可以正确地按照“左子树-根节点-右子树”的顺序遍历二叉树的所有节点。
算法题
-
1. 二叉树的中序遍历
leetcode官网地址:https://leetcode.cn/problems/binary-tree-inorder-traversal/description/
给定一个二叉树的根节点 root ,返回 它的 中序 遍历 。
示例 1:

输入:root = [1,null,2,3]
输出:[1,3,2]
示例 2:
输入:root = []
输出:[]
示例 3:
输入:root = [1]
输出:[1]
提示:
树中节点数目在范围 [0, 100] 内
-100 <= Node.val <= 100
进阶: 递归算法很简单,你可以通过迭代算法完成吗?
js代码实现 –递归
/**
* Definition for a binary tree node.
* function TreeNode(val, left, right) {
* this.val = (val===undefined ? 0 : val)
* this.left = (left===undefined ? null : left)
* this.right = (right===undefined ? null : right)
* }
*/
/**
* @param {TreeNode} root
* @return {number[]}
*/
var inorderTraversal = function (root) {
/// 定义一个数组
const arr = [];
const fun = (root) => {
if (!root) return;
// 遍历左子树
fun(root.left);
// 根
arr.push(root.val);
// 遍历有子树
fun(root.right);
}
fun(root);
return arr;
};
js代码实现 –非递归
/**
* Definition for a binary tree node.
* function TreeNode(val, left, right) {
* this.val = (val===undefined ? 0 : val)
* this.left = (left===undefined ? null : left)
* this.right = (right===undefined ? null : right)
* }
*/
/**
* @param {TreeNode} root
* @return {number[]}
*/
var inorderTraversal = function (root) {
// 定义一个数组
let arr = []
// 新建一个栈
let stack = []
// 存储根节点
let o = root
while (stack.length || o) { // 判断栈中是否有内容,以及是否存在根节点
while (o) {
stack.push(o)
o = o.left
}
let n = stack.pop()
arr.push(n.val)
o = n.right
}
return arr
};
二叉树的后序遍历
二叉树的后序遍历(Postorder Traversal)是一种按照“左子树-右子树-根节点”的顺序访问每个节点的方法。
具体步骤如下:
-
1. 从根节点开始。
-
2. 首先,递归地对根节点的左子树进行后序遍历。
-
3. 然后,递归地对根节点的右子树进行后序遍历。
-
4. 最后,访问根节点本身。
算法题
-
1. 二叉树的后序遍历
leetcode的地址:https://leetcode.cn/problems/binary-tree-postorder-traversal/description/
给你一棵二叉树的根节点 root ,返回其节点值的 后序遍历 。
示例 1:
输入:root = [1,null,2,3]
输出:[3,2,1]
示例 2:
输入:root = []
输出:[]
示例 3:
输入:root = [1]
输出:[1]
提示:
树中节点的数目在范围 [0, 100] 内
-100 <= Node.val <= 100
进阶:递归算法很简单,你可以通过迭代算法完成吗?
js实现方案–递归
/**
* Definition for a binary tree node.
* function TreeNode(val, left, right) {
* this.val = (val===undefined ? 0 : val)
* this.left = (left===undefined ? null : left)
* this.right = (right===undefined ? null : right)
* }
*/
/**
* @param {TreeNode} root
* @return {number[]}
*/
var postorderTraversal = function(root) {
let arr = [];
const fun = ( node )=>{
if( node ){
fun( node.left );
fun( node.right );
arr.push( node.val );
}
}
fun( root );
return arr;
};
s实现方案–非递归
/**
* Definition for a binary tree node.
* function TreeNode(val, left, right) {
* this.val = (val===undefined ? 0 : val)
* this.left = (left===undefined ? null : left)
* this.right = (right===undefined ? null : right)
* }
*/
/**
* @param {TreeNode} root
* @return {number[]}
*/
var postorderTraversal = function (root) {
// let arr = [];
// const fun = ( node )=>{
// if( node ){
// fun( node.left );
// fun( node.right );
// arr.push( node.val );
// }
// }
// fun( root );
// return arr;
if (!root) return [];
let arr = [];
let stack = [root];
while (stack.length) {
const o = stack.pop();
arr.unshift(o.val);
o.left && stack.push(o.left);
o.right && stack.push(o.right);
}
return arr;
};
其他算法题
二叉树的最小深度
leetcode地址:https://leetcode.cn/problems/minimum-depth-of-binary-tree/description/
给定一个二叉树,找出其最小深度。
最小深度是从根节点到最近叶子节点的最短路径上的节点数量。
说明:叶子节点是指没有子节点的节点。
示例 1:

输入:root = [3,9,20,null,null,15,7]
输出:2
示例 2:
输入:root = [2,null,3,null,4,null,5,null,6]
输出:5
提示:
树中节点数的范围在 [0, 10^5] 内
-1000 <= Node.val <= 1000
js解决方案
/**
* Definition for a binary tree node.
* function TreeNode(val, left, right) {
* this.val = (val===undefined ? 0 : val)
* this.left = (left===undefined ? null : left)
* this.right = (right===undefined ? null : right)
* }
*/
/**
* @param {TreeNode} root
* @return {number}
*/
var minDepth = function (root) {
// 如果没有根节点,则直接返回0
if (!root) return 0;
//新建一个栈
const stack = [[root, 1]];
while (stack.length) {
const [o, n] = stack.shift();
// 如果左子树和右子树没子节点,则返回
if (!o.left && !o.right) {
return n;
}
if (o.left) stack.push([o.left , n + 1]);
if (o.right) stack.push([o.right, n + 1]);
}
};
二叉树的最大深度
leetcode地址:https://leetcode.cn/problems/maximum-depth-of-binary-tree/description/
给定一个二叉树 root ,返回其最大深度。
二叉树的 最大深度 是指从根节点到最远叶子节点的最长路径上的节点数。
示例 1:

输入:root = [3,9,20,null,null,15,7]
输出:3
示例 2:
输入:root = [1,null,2]
输出:2
提示:
树中节点的数量在 [0, 104] 区间内。
-100 <= Node.val <= 100
js实现方案
/**
* Definition for a binary tree node.
* function TreeNode(val, left, right) {
* this.val = (val===undefined ? 0 : val)
* this.left = (left===undefined ? null : left)
* this.right = (right===undefined ? null : right)
* }
*/
/**
* @param {TreeNode} root
* @return {number}
*/
var maxDepth = function(root) {
if(!root) return 0 // 如果没有根节点,则直接返回0
// 找左右叉的最大值
return Math.max(maxDepth(root.left),maxDepth(root.right)) + 1
};
翻转二叉树
leetcode地址:https://leetcode.cn/problems/er-cha-shu-de-jing-xiang-lcof/description/
给定一棵二叉树的根节点 root,请左右翻转这棵二叉树,并返回其根节点。
示例 1:

输入:root = [5,7,9,8,3,2,4]
输出:[5,9,7,4,2,3,8]
提示:
树中节点数目范围在 [0, 100] 内
-100 <= Node.val <= 100
注意:本题与主站 226 题相同:https://leetcode-cn.com/problems/invert-binary-tree/
js代码解决方案
/**
* Definition for a binary tree node.
* function TreeNode(val) {
* this.val = val;
* this.left = this.right = null;
* }
*/
/**
* @param {TreeNode} root
* @return {TreeNode}
*/
var mirrorTree = function(root) {
// 如果根节点为空,则直接返回
if( root == null ) return null;
// 定义一个临时变量,暂存左子树
let tmp = root.left;
// 左右子树颠倒
root.left = root.right;
root.right = tmp;
mirrorTree(root.left);
mirrorTree(root.right);
return root;
};
相同的树
leetcode地址:https://leetcode.cn/problems/same-tree/description/
给你两棵二叉树的根节点 p 和 q ,编写一个函数来检验这两棵树是否相同。
如果两个树在结构上相同,并且节点具有相同的值,则认为它们是相同的。
示例 1:

输入:p = [1,2,3], q = [1,2,3]
输出:true
示例 2:

输入:p = [1,2], q = [1,null,2]
输出:false
示例 3:

输入:p = [1,2,1], q = [1,1,2]
输出:false
提示:
两棵树上的节点数目都在范围 [0, 100] 内
-10^4 <= Node.val <= 10^4
js代码解决方案
/**
* Definition for a binary tree node.
* function TreeNode(val, left, right) {
* this.val = (val===undefined ? 0 : val)
* this.left = (left===undefined ? null : left)
* this.right = (right===undefined ? null : right)
* }
*/
/**
* @param {TreeNode} p
* @param {TreeNode} q
* @return {boolean}
*/
var isSameTree = function (p, q) {
// 如果没有则返回true
if (p == null && q == null) return true
// 如果q == null 或者q == null 则返回false
if (p == null || q == null) return false
// 如果p.val 不等于 q。val 则返回false
if (p.val != q.val) return false
// 否则,递归处理o和q的左子树和右子树是否相同
return isSameTree(p.left, q.left) && isSameTree(p.right, q.right)
};
原文始发于微信公众号(前端爱好者):web前端算法简介之树-二叉树
版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。
文章由极客之音整理,本文链接:https://www.bmabk.com/index.php/post/267067.html