二叉树

西瓜皮儿 2021/12/18

# 手写二叉树

知识点

名词	知识点
节点	每个节点有左右两个子节点
满二叉树	除了最后一层，所有的节点都有2个子节点
二叉搜索树	左节点小于根节点，右节点大于根节点
前序遍历	根左右的顺序遍历
中序遍历	左根右【中序遍历的结果就是二叉搜索树排序的结果】
后序遍历	左右根

class Node {
    constructor(val) {
        this.val = val;
        this.left = null;
        this.right = null;
    }
}
class BST {
    size = 0;
    root = null;
    initNode(val) {
        return new Node(val);
    }
    append(val, root = this.root) {
        const node = this.initNode(val);
        if (!this.root) {
            this.size++;
            this.root = node;
            return this.root;;
        }
        if (val < root.val) {
            if (root.left) {
                this.append(val, root.left)
            } else {
                this.size++;
                root.left = node;
            }
        }
        if (val >= root.val) {
            if (root.right) {
                this.append(val, root.right)
            } else {
                this.size++;
                root.right = node;
            }
        }
        return root;
    }
    get(val, root = this.root) {
        if (!root) {
            return;
        }

        // 经典的二叉树递归搜索法
        if (val === root.val) {
            return root.val;
        }
        return val > root.val ? this.get(val, root.right) : this.get(val, root.left);
    }
    max(root = this.root) {
        if (!root) {
            return;
        }
        return (root.right ? this.max(root.right) : root).val
    }
    min(root = this.root) {
        return root?.left ? this.min(root.left) : root?.val;
    }
    deep(current = this.root, currentDeep = 0, maxDeep = 0) {
        if (!current) {
            return Math.max(currentDeep, maxDeep);
        }
        return Math.max(
            this.deep(current.left, currentDeep + 1, maxDeep),
            this.deep(current.right, currentDeep + 1, maxDeep)
        );
    }
    preOrder(cNode = this.root, ans = []) {
        if (!cNode) {
            return;
        }
        ans.push(cNode.val);
        this.preOrder(cNode.left, ans);
        this.preOrder(cNode.right, ans);
        return ans;
    }
    mediumOrder(cNode = this.root, ans = []) {
        if (!cNode) {
            return;
        }
        this.mediumOrder(cNode.left, ans);
        ans.push(cNode.val);
        this.mediumOrder(cNode.right, ans);
        return ans;
    }
    postOrder(cNode = this.root, ans = []) {
        if (!cNode) {
            return;
        }
        console.log(cNode);
        this.postOrder(cNode.left, ans);
        this.postOrder(cNode.right, ans);
        ans.push(cNode.val);
        return ans;
    }
    levelOrder() {
        if (!this.root) {
            return [];
        }
        const ans = [];
        const queue = [this.root];
        while (queue.length > 0) {
            const len = queue.length;
            ans.push(queue.map(item => item.val))
            for (let i = 0; i < len; i++) {
                const cNode = queue.shift();
                if (cNode.left) {
                    queue.push(cNode.left);
                }
                if (cNode.right) {
                    queue.push(cNode.right);
                }
            }
        }
        return ans;
    }
}
 
        复制成功

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
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117

# 最大深度

力扣 (opens new window)
返回3

1
2
3
4
5

时间【O(n)】:88.18%
空间【O(n)】:7.57%

var maxDepth = function(root) {
    if (!root) {
        return 0;
    }
    const queue = [];
    queue.push(root);
    let deep = 0;
    while (queue.length) {
        deep += 1;
        const len = queue.length;
        for (let i = 0; i < len; i++) {
            const cNode = queue.shift();
            if (cNode.left != null) {
                queue.push(cNode.left);
            }
            if (cNode.right != null) {
                queue.push(cNode.right);
            }
        }
    }
    return deep;
};
 
        复制成功

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

# 验证二叉搜索树

力扣 (opens new window)
给定节点看是否是二叉搜索树
1. 左子树小于当前节点
2. 右字树大于当前节点
3. 子树也是二叉搜索树

# 对称二叉树

力扣 (opens new window)
根据中轴左右对称

1
2
3
4
5

# 层序遍历

力扣 (opens new window)

    3
   / \
  9  20
    /  \
   15   7

// 输出
[
  [3],
  [9,20],
  [15,7]
]
 
        复制成功

1
2
3
4
5
6
7
8
9
10
11
12

# 中序遍历

力扣94 (opens new window)
求中序遍历

输入：root = [1,null,2,3]
输出：[1,3,2]
 
        复制成功

1
2

时间：76.74%
空间：41.39%

var inorderTraversal = function(root) {
    const ans = [];
    const deepHelper = (node) => {
        if (!node) {
            return;
        }
        if (node.left) {
            deepHelper(node.left);
        }
        ans.push(node.val)
        if (node.right) {
            deepHelper(node.right);
        }
    }
    deepHelper(root);
    return ans;
}
 
        复制成功

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

# 897. 递增顺序搜索树

给一棵二叉树，中序遍历生成新的二叉树，只有右节点，且递增，且每个节点没有左子节点

# 100. 相同的树

验证两棵树完全相同

# 589. N 叉树的前序遍历

给定一个 n叉树 的根节点 root ，返回其节点值的前序遍历。

# 257. 二叉树的所有路径

// root = [1,2,3,null,5]
const root = new TreeNode(
    1,
    new TreeNode(2, null, new TreeNode(5)),
    new TreeNode(3),
)
console.log(binaryTreePaths(root)); // [ '1->2->5', '1->3' ]
 
        复制成功

1
2
3
4
5
6
7

# 114. 二叉树展开为链表

按照先序遍历生成新的二叉树排序方式，所有节点只有右节点

const root = [1,2,5,3,4,null,6]
console.log(flatten(root));
// 输出：[1,null,2,null,3,null,4,null,5,null,6]
 
        复制成功

1
2
3

# 108. 将有序数组转换为二叉搜索树,回溯

一个整数数组 nums ，其中元素已经按升序排列，请你将其转换为一棵高度平衡二叉搜索树。

# 617. 合并二叉树

两个二叉树，两个对应节点都有值就相加，只有一边就使用那一边的值

const root1 = [1,3,2,5], root2 = [2,1,3,null,4,null,7];
console.log(mergeTrees(root1, root2));
// 输出：[3,4,5,5,4,null,7]
 
        复制成功

1
2
3

时间：86.72%
空间：5.14%

var mergeTrees = function(root1, root2) {
    if (!root1 && !root2) return null;
    const node = new TreeNode();
    if (root1 && root2) {
        node.val = root1.val + root2.val;
        node.left = mergeTrees(root1.left, root2.left);
        node.right = mergeTrees(root1.right, root2.right);
    } else if(root1) {
        node.val = root1.val;
        node.left = mergeTrees(root1.left, null);
        node.right = mergeTrees(root1.right, null);
    } else {
        node.val = root2.val;
        node.left = mergeTrees(root2.left, null);
        node.right = mergeTrees(root2.right, null);
    }
    return node;
};
 
        复制成功

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

# 116. 填充每个节点的next指针

注意判断剪枝if (!left || left.next)避免重复操作，优化时间效率

时间：88.86%
空间：72.95%

function connect(root) {
    if (!root) return null;
    const handler = (left, right) => {
        if (!left || left.next) return;
        left.next = right;
        handler(left.left, left.right);
        handler(left.right, right.left);
        handler(right.left, right.right);
    }
    handler(root.left, root.right);
    return root;
}
 
        复制成功

1
2
3
4
5
6
7
8
9
10
11
12

时间：空间：

function connect(root) {
    if (!root) return null;
    const queue = [root];
    while (queue.length) {
        let len = queue.length;
        for (let i = 0; i < len; i++) {
            const node = queue.shift();
            node.next = i < len - 1 ? queue[0] : null;
            if (node.left) queue.push(node.left);
            if (node.right) queue.push(node.right);
        }
    }
    return root;
}
 
        复制成功

1
2
3
4
5
6
7
8
9
10
11
12
13
14

# 124. 二叉树中的最大路径和

求最大和的路径，路径起点可以是任意节点

const root = [1,2,3]
console.log(maxPathSum(root));
// 输出：6
 
        复制成功

1
2
3

# 236. 二叉树的最近公共祖先

给定一个二叉树和两个节点，寻找这两个节点的最近的公共祖先（必定存在）（有可能是自身）

哈希表常见排序