抱歉,您的浏览器无法访问本站

本页面需要浏览器支持(启用)JavaScript


了解详情 >

二叉树

二叉树遍历

  • 前序:根节点 => 左子树 => 右子树
  • 中序:左子树 => 根节点 => 右子树
  • 后序:左子树 => 右子树 => 根节点
  • 层序:按照每层的节点进行遍历
  • 通过遍历序列获取树结构:前、后、层序都能确定顶部节点,中序能够根据顶部节点确定左右子树,所以通过遍历序列获取树结构时必须要有前、后、层三者之一,以及中序序列
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
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
// 前序、中序、后序遍历,调整内部函数的递归顺序即可。示例为后序
function orderTraversal( root ) {
// write code here
let result = []
function traversal(node){
if(node == null) return
traversal(node.left)
traversal(node.right)
result.push(node.val)
}
afterTraversal(root)
return result
}
// 层级遍历
function levelOrder(root) {
let result = [];
let dfs = (root, index) => {
if (!root) {
return;
}
if (!result[index]) {
result[index] = [];
}
result[index].push(root.val);
dfs(root.left, index + 1);
dfs(root.right, index + 1);
};
dfs(root, 0);
return result;
}
// 序列化二叉树
function TreeNode(x) {
this.val = x;
this.left = null;
this.right = null;
}
function Serialize(pRoot, arr = []) {
// write code here
if (!pRoot) {
arr.push("#");
return arr;
} else {
arr.push(pRoot.val);
Serialize(pRoot.left, arr);
Serialize(pRoot.right, arr);
}
return arr;
}
function Deserialize(s) {
// write code here
let arr =
let a = arr.shift();
let node = null;
if (typeof a === "number") {
node = new TreeNode(a);
node.left = Deserialize(arr);
node.right = Deserialize(arr);
}
return node;
}
module.exports = {
Serialize: Serialize,
Deserialize: Deserialize,
};

二叉树的操作也是基于上述遍历进行运算。

二叉搜索树转双向链表

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
// 利用栈,非常巧妙的完成了较小节点的暂存
function Convert(pRootOfTree)
{
// write code here

if(!pRootOfTree) return null
let stack = [],p = pRootOfTree,pre = null,isFirst = true
while(p||stack.length>0){
while(p){
stack.push(p)
p = p.left
}
p = stack.pop()
if(isFirst){
pRootOfTree = p
pre = pRootOfTree
isFirst = false
}else{
pre.right = p
p.left = pre
pre = p
}
p = p.right
}
return pRootOfTree
}

二叉树的特殊类型

二叉搜索树:左侧子树的值都小于根节点的值,右侧子树的值都大于根节点的值

完全二叉树:除二叉树叶子节点层,所有层都没有空缺节点,且叶子节点从左到右连续没有空缺

平衡二叉树:是空树或者左右子树的高度差绝对值不超过1,且左右子树都是平衡二叉树

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
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
// 判断二叉搜索树
const helper = (root, lower, upper) => {
if (root === null) {
return true;
}
if (root.val <= lower || root.val >= upper) {
return false;
}
return helper(root.left, lower, root.val) && helper(root.right, root.val, upper);
}
var isValidBST = function(root) {
return helper(root, -Infinity, Infinity);
};

// 判断完全二叉树
function isCompleteTree( root ) {
// write code here
if(root == null) return true;

const queue = [];
queue.push(root);

let flag = false;
while(queue.length) {
const node = queue.shift();
if(node == null) {
flag = true;
continue;
}

if(flag == true) {
return false;
}

queue.push(node.left);
queue.push(node.right);
}
return true;
}
// 判断平衡二叉树
function IsBalanced_Solution(pRoot)
{
if(!pRoot) return true;
// write code here
return (Math.abs(getMaxDepth(pRoot.left) - getMaxDepth(pRoot.right)) <=1) && IsBalanced_Solution(pRoot.left) && IsBalanced_Solution(pRoot.right)
}

function getMaxDepth(root) {
if(!root) return 0;
return Math.max(getMaxDepth(root.left)+1,getMaxDepth(root.right)+1)
}

评论