（LeetCode）二叉树_definition for a binary tree node.

0. 总结

二叉树的核心就是用递归的思想解决问题，三个要素分析清楚：

1. 寻求递归的子问题，子问题就是要解决的问题落实到一个（带左右孩子的）节点上时应该怎么做；
2. 递归终止条件；
3. 递归返回值；

1. 合并二叉树

617. merge-two-binary-trees

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution(object):

    def mergeTrees(self, t1, t2):
        """
        :type t1: TreeNode
        :type t2: TreeNode
        :rtype: TreeNode

        """
        if t1 is None:
            return t2
        if t2 is None:
            return t1
        
        t1.val += t2.val
        t1.left = self.mergeTrees(t1.left, t2.left)
        t1.right = self.mergeTrees(t1.right, t2.right)

        return t1

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. 翻转二叉树

226. invert-binary-tree

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution(object):
    def invertTree(self, root):
        """
        :type root: TreeNode
        :rtype: TreeNode
        """
        if root is None:
            return None

        root.left, root.right = root.right, root.left
        self.invertTree(root.left)
        self.invertTree(root.right)

        return root

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

3. 二叉树的最大深度

104. maximum-depth-of-binary-tree

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution(object):
    def maxDepth(self, root):
        """
        :type root: TreeNode
        :rtype: int
        """
        if root is None:
            return 0

        return 1 + max(self.maxDepth(root.left), self.maxDepth(root.right))

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

4. 把二叉搜索树转换为累加树

538. convert-bst-to-greater-tree

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution(object):
    def __init__(self):
        self.acc = 0

    def convertBST(self, root):
        """
        :type root: TreeNode
        :rtype: TreeNode

        二叉树遍历：右 根 左
        """
        if root is None:
            return None
        
        self.convertBST(root.right)
        root.val += self.acc
        self.acc = root.val
        self.convertBST(root.left)

        return root
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

5. 对称二叉树

101. symmetric-tree

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution(object):
    def isSymmetric(self, root):
        """
        :type root: TreeNode
        :rtype: bool
        
        笨办法
            分别 根左右、根右左 遍历这棵树，比较生成的元素是否一一相等
            (注意遍历的时候None也要考虑进去)
        
        聪明办法
            两个指针指向同一棵树，同步移动，一个向左、一个向右，检查是否相等

        """

        def check_node(t1, t2):
            if not t1 and not t2:
                return True
            if not t1 or not t2:
                return False
            return t1.val == t2.val and check_node(t1.left, t2.right) and check_node(t1.right, t2.left)
        
        return check_node(root, root)

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

6. 二叉树的直径

543. diameter-of-binary-tree

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution(object):

    def __init__(self):
        self.max_path_len = 0

    def diameterOfBinaryTree(self, root):
        """
        :type root: TreeNode
        :rtype: int

        解法
            任意两节点的路径都可以表示为 以某个节点为根的左右子树深度之和
            最长直径，就是由 左右子树深度之和最大的子树(以任意节点为根) 产生的
        """
        # 笨办法递归
        # def max_depth(root):
        #     if not root:
        #         return 0
        #     return 1 + max(max_depth(root.left), max_depth(root.right))
        
        # if not root:
        #     return 0
        # path_len = max_depth(root.left) + max_depth(root.right)
        # self.max_path_len = max(self.max_path_len, path_len)
        # self.diameterOfBinaryTree(root.left)
        # self.diameterOfBinaryTree(root.right)

        # return self.max_path_len

        # 在求数最大深度递归算法的基础上增加求极值
        def max_depth(root):
            if not root:
                return 0
            l_depth = max_depth(root.left)
            r_depth = max_depth(root.right)
            self.max_path_len = max(self.max_path_len, l_depth+r_depth)
            return 1 + max(l_depth, r_depth)

        max_depth(root)
        return self.max_path_len

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

7. 二叉树的中序遍历

94. binary-tree-inorder-traversal

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution(object):
    def inorderTraversal(self, root):
        """
        :type root: TreeNode
        :rtype: List[int]

        思路
            递归算法简单

            非递归用循环和栈实现
        """

        result = []
        stack = []
        node = root
        while node or stack:
            while node:
                stack.append(node)  # 左链入栈
                node = node.left
            node = stack.pop()
            result.append(node.val)  # 输出
            node = node.right  # 右链
        return result

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

8. 二叉树展开为链表

114. flatten-binary-tree-to-linked-list

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution(object):
    def flatten(self, root):
        """
        :type root: TreeNode
        :rtype: None Do not return anything, modify root in-place instead.

        思路
            先序遍历二叉树, 将结果保存到一个数组
            迭代数组, 重链指针

            或者使用后序遍历, 直接在traverse内部重链, 需使用一个全局变量pre
        """
        def traverse(root, array):
            if not root:
                return
            array.append(root)
            traverse(root.left, array)
            traverse(root.right, array)

        array = []
        traverse(root, array)

        for i in range(len(array)-1):
            array[i].left = None
            array[i].right = array[i+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

9. 从前序与中序遍历序列构造二叉树

105. construct-binary-tree-from-preorder-and-inorder-traversal

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution(object):
    def buildTree(self, preorder, inorder):
        """
        :type preorder: List[int]
        :type inorder: List[int]
        :rtype: TreeNode

        思路
            前序遍历：[ 根节点, [左子树的前序遍历结果], [右子树的前序遍历结果] ]
            中序遍历：[ [左子树的中序遍历结果], 根节点, [右子树的中序遍历结果] ]
            根据前序遍历拿到根节点, 用根节点到中序遍历结果find, 找到左子树结果与右子树结果分界点
            递归对左右子树, 以同样的方式构建
        """

        if not preorder or not inorder:
            return None
        
        node = TreeNode(preorder[0])
        node_idx = inorder.index(preorder[0])
        node.left = self.buildTree(preorder[1:node_idx+1], inorder[:node_idx])
        node.right = self.buildTree(preorder[node_idx+1:], inorder[node_idx+1:])

        return node

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

10. 不同的二叉搜索树

96. unique-binary-search-trees

class Solution(object):
    def numTrees(self, n):
        """
        :type n: int
        :rtype: int

        思路
            题目满足卡塔兰数, 请参考下面资料
            https://baike.baidu.com/item/catalan/7605685?fr=aladdin
            https://leetcode-cn.com/problems/unique-binary-search-trees/solution/bu-tong-de-er-cha-sou-suo-shu-by-leetcode/
        """
        C = 1
        for i in range(0, n):
            C = C * 2*(2*i+1)/(i+2)
        return int(C)

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

11. 二叉树的最近公共祖先

236. lowest-common-ancestor-of-a-binary-tree

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution(object):
    def lowestCommonAncestor(self, root, p, q):
        """
        :type root: TreeNode
        :type p: TreeNode
        :type q: TreeNode
        :rtype: TreeNode

        思路
            将每个节点的父节点存到一个字典里面,
            分别从p, q两个节点往上走, 最先相遇的即是最近公共祖先
        """

        def save_parents(root):
            if not root:
                return
            if root.left:
                parents[root.left] = root
            if root.right:
                parents[root.right] = root
            save_parents(root.left)
            save_parents(root.right)
        
        def get_node_parents(node):  # 获取node的所有父亲, 从近到远, 包含自身
            node_parents = [node]
            while node in parents:
                node_parents.append(parents[node])
                node = parents[node]
            return node_parents
        
        parents = {}
        save_parents(root)

        p_parents, q_parents = get_node_parents(p), get_node_parents(q)
        for i in range(min(len(p_parents), len(q_parents))):  # p和q属于不同子树
            if p_parents[-i-1] == q_parents[-i-1]:
                continue
            return p_parents[-i]
        # p和q在同棵子树
        nearest_parent = p_parents[0] if len(p_parents) < len(q_parents) else q_parents[0]

        return nearest_parent

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

12. 二叉树的层序遍历

102. binary-tree-level-order-traversal

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution(object):
    def levelOrder(self, root):
        """
        :type root: TreeNode
        :rtype: List[List[int]]

        思路
            带栈深度地遍历二叉树, 将节点按栈深保存到result
        """
        def traverse(root, depth, result):
            if not root:
                return
            if depth >= len(result):
                result.append([])
            result[depth].append(root.val)
            traverse(root.left, depth+1, result)
            traverse(root.right, depth+1, result)
        
        result = []
        traverse(root, 0, result)
        
        return result

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

13. 路径总和 III

437. path-sum-iii

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution(object):

    def __init__(self):
        self.path_num = 0

    def pathSum(self, root, sum):
        """
        :type root: TreeNode
        :type sum: int
        :rtype: int

        思路
        	两重递归
            1. 从根节点开始遍历，计算满足条件的路径条数；(假设路径一定从根节点开始)
            2. 分别以所有节点为根节点，计算路径总条数；
        """
        if root is None:
            return 0

        self.path(root, sum)
        self.pathSum(root.left, sum)
        self.pathSum(root.right, sum)

        return self.path_num
        
    def path(self, root, sum):
        if root is None:
            return
        
        sum -= root.val
        if sum == 0:
            self.path_num += 1
        
        self.path(root.left, sum)
        self.path(root.right, sum)

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