首页算法

[toc]

# 二叉树基础

# 一、二叉树种类

# 1. 满二叉树

除最后一层有两个子节点外，最后一层没有子节点，如果某个满二叉树有 k 层则该满二叉树有 2 的 k 次方 - 1 个节点。

# 2. 完全二叉树

最后一层如果有缺的子节点则该子节点为右侧的子节点。如果某个完全二叉树有 k 层，则该完全二叉树则有 2 的 k-1 次方到 2 的 k 次方 - 1 个节点。满二叉树是特殊的完全二叉树

# 3. 二叉搜索树

二叉搜索树中某个节点的左节点值小于该节点，右节点值大于该节点

# 4. 二叉平衡树

在二叉搜索树的条件下，每一个节点的左子树与右子树的高度差不大于一，二叉平衡树是特殊的二叉搜索树。另外二叉树的高度从下往上数，深度从上往下数。

# 二、 二叉树的构建

# 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
在做力扣上102. 二叉树的层序遍历的时候，好奇试了一下console.dir(root)
TreeNode {
  val: 3,
  left: TreeNode { val: 9, left: null, right: null },
  right: TreeNode {
    val: 20,
    left: TreeNode { val: 15, left: null, right: null },
    right: TreeNode { val: 7, left: null, right: null }
  }
}// 结果是这个，根据这个我试着构建了一下二叉树，当然后面看别人的文章发现二叉树远不止这些属性和方法
class TreeNode {
    constructor(val) {
      this.val = val;
      this.left = null;
      this.right = null;
    }
    addleft(left){
        this.left = left
    }
    addright(right){
        this.right = right
    }
}
const root = new TreeNode(3)
root.addleft(new TreeNode(9))
root.addright(new TreeNode(20))
root.right.addleft(new TreeNode(15))
root.right.addright(new TreeNode(7))

# 三、二叉树的遍历

# 1. 深度优先算法

# 1. 递归法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
//root为二叉树
const result =[]
const dfs = (root)=>{
    if(root==null) return
    //前序遍历
    result.push(root.val)
    dfs(root.left)
    dfs(root.right)
    //中序遍历
    dfs(root.left)
    result.push(root.val)
    dfs(root.right)
    //后序遍历
    dfs(root.left)
    dfs(root.right)
    result.push(root.val)
}
dfs(root)
return result

# 2. 迭代法

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
//前序遍历
const result =[],arr=[root]
while(arr.length>0){
    let tree = arr.pop()
    if(tree==null) continue
    result.push(tree.val)
	arr.push(tree.right)
    arr.push(tree.left)
}
return result
//后序遍历 在前序遍历的情况下调换调换传入arr的两个子节点，同时将最后的数组反转。
const result =[],arr=[root]
while(arr.length>0){
    let tree = arr.pop()
    if(tree==null) continue
    result.push(tree.val)
    arr.push(tree.left)
    arr.push(tree.right)
}
return result.reverse()
//中序遍历
const result =[],stack=[]
let tree = root
while(stack.length>0||tree){
	if(tree){
		stack.push(tree)
		tree = tree.left
	}else{
		let rootTree = stack.pop()
		result.push(rootTree.val)
		tree = rootTree.right
	}
}
return result

# 2. 广度优先搜索(层序遍历)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
//力扣上的层序遍历最后的输出结果似乎都是二维数组，需要将每一层的值用数组储存然后将其储存进一个数组输出出去。
const result = [],arr=[root]
let res=[]
while(arr.length>0){
    let len = arr.length //相当于快照用于储存当前层数的长度。
    while(len>0){ //当len为零时，说明当前层的值已全部弹出，这时应该用result储存当前层所有数组
        let tree = arr.shift() 
        len -- 
        if(tree!=null){
            res.push(tree.val)
            arr.push(tree.left)
            arr.push(tree.right)  
        }     
    }
    if(res.length==0) break 
    result.push(res) 
    res = [] //清空当前层用于记录下一层的值
}
return result