# 二叉树
# 介绍
树 是一种经常用到的数据结构，用来模拟具有树状结构性质的数据集合。
树里的每一个节点有一个根植和一个包含所有子节点的列表。从图的观点来看，树也可视为一个拥有N 个节点和N-1 条边的一个有向无环图。
二叉树是一种更为典型的树树状结构。如它名字所描述的那样，二叉树是每个节点最多有两个子树的树结构，通常子树被称作“左子树”和“右子树”。
# 前序遍历
前序遍历首先访问根节点，然后遍历左子树，最后遍历右子树。
递归实现
/**
* Definition for a binary tree node.
* function TreeNode(val) {
* this.val = val;
* this.left = this.right = null;
* }
*/
/**
* @param {TreeNode} root
* @return {number[]}
*/
var preorderTraversal = function(root) {
var res = [];
_preOrder(root);
function _preOrder(node) {
if (node === null) {
return;
}
res.push(node.val);
_preOrder(node.left);
_preOrder(node.right);
}
return res;
};
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
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
非递归前序遍历(深度优先)
/**
* Definition for a binary tree node.
* function TreeNode(val) {
* this.val = val;
* this.left = this.right = null;
* }
*/
/**
* @param {TreeNode} root
* @return {number[]}
*/
var preorderTraversal = function(root) {
var res = [];
var stack = [];
if (root === null) {
return [];
}
stack.push(root);
while (stack.length) {
var node = stack.pop();
res.push(node.val);
if (node.right !== null) {
stack.push(node.right);
}
if (node.left !== null) {
stack.push(node.left);
}
}
return res;
};
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
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
# 中序遍历
递归实现
/**
* Definition for a binary tree node.
* function TreeNode(val) {
* this.val = val;
* this.left = this.right = null;
* }
*/
/**
* @param {TreeNode} root
* @return {number[]}
*/
var inorderTraversal = function(root) {
var res = [];
_inOrder(root);
function _inOrder(node) {
if (node === null) {
return;
}
_inOrder(node.left);
res.push(node.val);
_inOrder(node.right);
}
return res;
};
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
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
后序遍历
递归实现
/**
* Definition for a binary tree node.
* function TreeNode(val) {
* this.val = val;
* this.left = this.right = null;
* }
*/
/**
* @param {TreeNode} root
* @return {number[]}
*/
var postorderTraversal = function(root) {
var res = [];
_postOrder(root);
function _postOrder(node) {
if (node === null) {
return;
}
_postOrder(node.left);
_postOrder(node.right);
res.push(node.val);
}
return res;
};
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
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
# 层序遍历
层序遍历就是逐层遍历树结构。
广度优先搜索是一种广泛运用在树或图这类数据结构中，遍历或搜索的算法。 该算法从一个根节点开始，首先访问节点本身。 然后遍历它的相邻节点，其次遍历它的二级邻节点、三级邻节点，以此类推。
当我们在树中进行广度优先搜索时，我们访问的节点的顺序是按照层序遍历顺序的。
给定二叉树: [3,9,20,null,null,15,7],
3
/ \
9 20
/ \
15 7
1
2
3
4
5
2
3
4
5
返回其层次遍历结果：
[[3], [9, 20], [15, 7]];
1
通常，我们使用一个叫做队列的数据结构来帮助我们做广度优先搜索。
/**
* Definition for a binary tree node.
* function TreeNode(val) {
* this.val = val;
* this.left = this.right = null;
* }
*/
/**
* @param {TreeNode} root
* @return {number[][]}
*/
var levelOrder = function(root) {
var queue = [];
var res = [];
if (root === null) {
return [];
}
queue.push(root);
while (queue.length) {
var size = queue.length;
var levelRes = [];
for (var i = 0; i < size; i++) {
var node = queue.shift();
levelRes.push(node.val);
if (node.left !== null) {
queue.push(node.left);
}
if (node.right !== null) {
queue.push(node.right);
}
}
res.push(levelRes);
}
return res;
};
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
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
# 二叉树最大深度
/**
* Definition for a binary tree node.
* function TreeNode(val) {
* this.val = val;
* this.left = this.right = null;
* }
*/
/**
* @param {TreeNode} root
* @return {number}
*/
var maxDepth = function(root) {
var queue = [];
var maxDepth = 0;
if (root === null) {
return maxDepth;
}
queue.push(root);
while (queue.length) {
maxDepth++;
var size = queue.length;
for (var i = 0; i < size; i++) {
var node = queue.shift();
if (node.left !== null) {
queue.push(node.left);
}
if (node.right !== null) {
queue.push(node.right);
}
}
}
return maxDepth;
};
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
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
# 对称二叉树
给定一个二叉树，检查它是否是镜像对称的。
例如，二叉树 [1,2,2,3,4,4,3] 是对称的。
1
/ \
2 2
/ \ / \
3 4 4 3
1
2
3
4
5
2
3
4
5
对于一个节点，要满足他两个孩子是相同的，并且左孩子的左孩子与右孩子的右孩子要相等，左孩子的右孩子要和右孩子的左孩子相等，递归实现。
/**
* Definition for a binary tree node.
* function TreeNode(val) {
* this.val = val;
* this.left = this.right = null;
* }
*/
/**
* @param {TreeNode} root
* @return {boolean}
*/
var isSymmetric = function(root) {
if (root === null) return true;
return _isSymmetric(root.left, root.right);
function _isSymmetric(leftChild, rightChild) {
if (leftChild == null && rightChild == null) return true;
if (leftChild == null && rightChild != null) return false;
if (leftChild != null && rightChild == null) return false;
if (leftChild.val != rightChild.val) return false;
return (
_isSymmetric(leftChild.left, rightChild.right) &&
_isSymmetric(leftChild.right, rightChild.left)
);
}
};
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
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
# 路径总和
给定一个二叉树和一个目标和，判断该树中是否存在根节点到叶子节点的路径，这条路径上所有节点值相加等于目标和。
说明: 叶子节点是指没有子节点的节点。
示例:
给定如下二叉树，以及目标和 sum = 22，
5
/ \
4 8
/ / \
11 13 4
/ \ \
7 2 1
1
2
3
4
5
6
7
2
3
4
5
6
7
返回 true, 因为存在目标和为 22 的根节点到叶子节点的路径 5->4->11->2。
/**
* Definition for a binary tree node.
* function TreeNode(val) {
* this.val = val;
* this.left = this.right = null;
* }
*/
/**
* @param {TreeNode} root
* @param {number} sum
* @return {boolean}
*/
var hasPathSum = function(root, sum) {
return _hasPathSum(root, sum, 0);
function _hasPathSum(root, sum, curSum) {
if (root === null) return false;
curSum += root.val;
if ((root.left === null && root.right === null) && curSum === sum) {
return true;
}
return (
_hasPathSum(root.left, sum, curSum) ||
_hasPathSum(root.right, sum, curSum)
);
}
};
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
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