应用场景广泛，可惜我个小菜鸟几乎全跪！！！如何提高？
二叉树和二叉搜索树
二叉树: 书中的节点最多只能有2个节点，一个是左侧子节点，一个是右侧子节点
二叉搜索树(BST): 二叉树种的一种，但是只允许你在左侧存储比父节点小的值，右侧存储比父节点大的值
两颗相同的树
题目:
给你两棵二叉树的根节点 p 和 q ，编写一个函数来检验这两棵树是否相同。如果两个树在结构上相同，并且节点具有相同的值，则认为它们是相同的。
答案:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
|
var isSameTree = function(p, q) {
if (p == null && q == null) {
return true
}
if (p == null || q == null) {
return false
}
return p.val === q.val && isSameTree(p.right, q.right) && isSameTree(p.left, q.left)
};
|
链接: 100. 相同的树
二叉搜索树的中序遍历
中序遍历是一种上行顺序访问树中所有节点的遍历方式
中序遍历的应用场景就是对树进行排序，也就是一从最小到最大的顺序访问所有子节点
题目: 给定一个二叉树的根节点 root ，返回它的 中序 遍历。
解题1 递归遍历
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
|
var inorderTraversal = function(root) {
const arr = []
const inOder = (node) => {
if(node !== null) {
inOder(node.left)
arr.push(node.val)
inOder(node.right)
}
}
inOder(root)
return arr
};
|
解题2 迭代遍历
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
| inOrderTravserseIterator(root) {
const res = [];
const stack = []
while(root) {
stack.push(root)
root= root.left
}
while(stack.length) {
const current = stack.pop();
res.push(current.val)
current = current.right;
while(current) {
stack.push(current)
current = current.left
}
}
return res
}
|
链接：
二叉树先序遍历
优先以后代节点的顺序访问每个节点的，跟中序不一样的是，先序遍历会优先访问节点本身，然后在访问她的左侧节点，最后是右侧子节点
应用场景是打印一个结构化的文档
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
|
var preorderTraversal = function(root) {
const arr = []
const inOder = (node) => {
if(node !== null) {
arr.push(node.val)
inOder(node.left)
inOder(node.right)
}
}
inOder(root)
return arr
};
|
后序遍历
先访问节点的后代节点，在访问节点本身，应用场景主要是计算一个目录及其子目录中所有文件所占空间的大小
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
|
var postorderTraversal = function(root) {
const arr = []
const postOrder = (node) => {
if (node !== null) {
postOrder(node.left)
postOrder(node.right)
arr.push(node.val)
}
}
postOrder(root)
return arr
};
|
层序遍历、
给你一个二叉树，请你返回其按 层序遍历 得到的节点值。 （即逐层地，从左到右访问所有节点）。
示例：
二叉树：[3,9,20,null,null,15,7],
得到:
1
2
3
4
5
| [
[3],
[9,20],
[15,7]
]
|
广度遍历bfs
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
|
var levelOrder = function(root) {
if (root == null) {return []};
let queue = [root]
let res = []
while(queue.length > 0) {
let len = queue.length;
let arr = []
for( let i = 0; i < len; i ++) {
let node = queue.shift()
arr.push(node.val);
if (node.left) {
queue.push(node.left)
}
if(node.right) {
queue.push(node.right)
}
}
res.push(arr)
}
return res
};
|
dfs深度遍历
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
| levelOrderdfs() {
if (!this.root) {return []}
const res = [];
const dfs = (node, step, res) => {
if (node !== null) {
if (!res[step]) {
res[step] = []
}
res[step].push(node.key)
dfs(node.left, step + 1, res);
dfs(node.right, step + 1, res);
}
}
dfs(this.root, 0, res)
return res;
}
|
二叉树的最大深度
给定一个二叉树，找出其最大深度。
二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。
说明: 叶子节点是指没有子节点的节点。
示例：
给定二叉树 [3,9,20,null,null,15,7]，
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/maximum-depth-of-binary-tree
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
递归的结束条件：当遍历到 null 节点，它们的高度是 0，返回 0。
1
2
3
4
5
6
7
8
9
10
11
12
13
|
var maxDepth = function(root) {
if (root == null) {
return 0
} else {
const leftMaxDepth = maxDepth(root.left);
const rightMaxDepth = maxDepth(root.right);
return 1 + Math.max(leftMaxDepth, rightMaxDepth)
}
};
|
最小深度
给定一个二叉树，找出其最小深度。
最小深度是从根节点到最近叶子节点的最短路径上的节点数量。
说明：叶子节点是指没有子节点的节点。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
|
var minDepth = function(root) {
if (root == null) {
return 0
} else if (root.left == null) {
return 1 + minDepth(root.right);
} else if (root.right == null) {
return 1 + minDepth(root.left);
} else {
return 1 + Math.min(minDepth(root.right), minDepth(root.left))
}
};
|
二叉树所有路径
给定一个二叉树，返回所有从根节点到叶子节点的路径。
说明: 叶子节点是指没有子节点的节点。
实例:
1
2
3
4
5
6
7
8
9
10
11
12
|
输入:
1
/ \
2 3
\
5
输出: ["1->2->5", "1->3"]
解释: 所有根节点到叶子节点的路径为: 1->2->5, 1->3
|
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/binary-tree-paths
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
