LeetCode刷题：树专题_leetcode刷题树

【1】面试题 04.04. 检查平衡性

考点： 递归

思路1： 从顶向下，若根节点的左右子树高度相差小于等于1（即是平衡树），则递归向下检查每个子树是否也为平衡树。
思路2： 自底向上，判断各子树是否为平衡树，一旦非平衡树那就没必要继续往上判断，直接返回 False。

分析： 可以发现思路 1 是存在很大的计算冗余的，从根节点向下判断时，每次都要重复计算子树高度，而且越靠下层的节点被重复计算的次数越多。此时自底向上是最优选择，每个节点都只参与了一次计算。

思路1： 从顶向下

对于 depth 函数来说，确定函数功能：求当前子树的高度；确定递归边界：当 root 为空时，返回树高度等于 0。
对于 isBalanced 函数来说，确定函数功能：判断当前子树是否为平衡树（左右子树高度差是否小于等于 1）；确定递归边界：当 root 为空时，说明树为平衡树。

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

class Solution:
    def isBalanced(self, root: TreeNode) -> bool:

        def depth(root):
            if not root: return 0   # 递归边界
            return max(depth(root.left), depth(root.right)) + 1

        if not root: return True
        if abs(depth(root.left) - depth(root.right)) <= 1:
            return self.isBalanced(root.left) and self.isBalanced(root.right)
        return False
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

思路2： 自底向上

这里只有一个递归就是 depth，确定函数功能：判断当前子树是否为平衡树（左右子树高度差是否小于等于 1），若非平衡树则返回 -1，否则返回当前树的高度；确定递归边界：当 root 为空时，返回树高度等于 0。

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

class Solution:
    def isBalanced(self, root: TreeNode) -> bool:

        def depth(root):
            if not root: return 0
            left = depth(root.left)
            if left == -1: return -1
            right = depth(root.right)
            if right == -1: return -1
            if abs(left - right) > 1:
                return -1
            return max(left, right) + 1

        if not root: return True
        return depth(root) != -1
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

---

【2】530. 二叉搜索树的最小绝对差

考点： 二叉搜索树中序遍历（递归实现与非递归实现）

思路1： 中序遍历二叉树，生成一个递增的列表，然后循环遍历该列表，计算每两个相邻元素的差，取所有差的最小值即可。
思路1： 中序遍历二叉树的同时，记录除了第一个节点之外每个节点的前一个节点，用于计算差值，用当前差值和最小值进行比较，取较小值即可。

分析： 中序遍历二叉搜索树得到的序列是一个递增序列。这是二叉搜索树的一个重要性质，巧妙利用这一性质可以解决一系列二叉搜索树问题。

【非递归中序遍历二叉搜索树模板】

p = root
st = []  # 用列表模拟实现栈的功能
while p or st:
    while p:
        st.append(p)
        p = p.left
    p = st.pop()
    process(p.val)  # 自己定义的一些操作
    p = p.right
1
2
3
4
5
6
7
8
9

思路1： 递归中序遍历二叉搜索树，生成递增列表；循环计算列表相邻两数的差值，取所有差值中的最小值。时间复杂度：O(n^2)

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

class Solution:
    def getMinimumDifference(self, root: TreeNode) -> int:
        
        def inOrder(root):
            if not root: return
            inOrder(root.left)
            nums.append(root.val)
            inOrder(root.right)
            return nums

        nums = []
        nums = inOrder(root)
        length = len(nums)
        minima = nums[1] - nums[0]
        for i in range(length-1):
            res = nums[i+1] - nums[i]
            if res < minima:
                minima = res
        return minima
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： 用栈实现非递归中序遍历二叉搜索树，保存每个节点的前一节点值，计算差值并取最小。对于最小值和前一节点的初始化，分别设置有正无穷大和负无穷大。时间复杂度：O(n)

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

class Solution:
    def getMinimumDifference(self, root: TreeNode) -> int:
        st = []
        p = root
        pre = -float('inf')   # 前一节点
        min_val = float('inf')  # 最小值
        while p is not None or st:
            while p is not None:
                st.append(p)
                p = p.left
            p = st.pop()
            cur = p.val
            if cur - pre < min_val:
                min_val = cur - pre
            pre = cur
            p = p.right
        return min_val

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

参考文章：中序遍历团灭系列二叉搜索树问题

---

【3】538. 把二叉搜索树转换为累加树

考点： 二叉搜索树中序遍历（递归实现与非递归实现）

思路1： 递归反序中序遍历。“右根左”遍历二叉搜索树，一边遍历一边计算累加值并修改树节点。
思路2： 非递归反序中序遍历。同思路1。
思路3： 反序中序 Morris 遍历。参考：把二叉搜索树转换为累加树，实现 O(1) 的空间复杂度。

分析： 实际上仍然是二叉搜索树的中序遍历，只不过正向中序是递增，这里考了个递减的反向中序。

思路1： 反序中序遍历，通过“右根左”遍历二叉搜索树就可以得到一个递减的数列，由于每个树节点都要加上所有比它大的数，通过这样的递减遍历，只需要用 total 全局变量记录当前所遇到的所有节点之和，并累加到当前节点上，就能实现累加树结构。时间复杂度：O(n)，每个节点最多被遍历一次；空间复杂度：O(n)，最坏情况下树只有左/右子树，调用栈会一直向下到 n。

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

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

    def convertBST(self, root):
        if not root: return root
        self.convertBST(root.right)
        self.total += root.val
        root.val = self.total
        self.convertBST(root.left)
        return root
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
'
运行
运行

思路2： 用栈实现非递归中序遍历二叉搜索树，思路其实和递归是一样的。时间复杂度：O(n)，每个节点会被压入栈中一次；空间复杂度：O(n)，栈的大小就是树节点的个数。

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

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

    def convertBST(self, root):
        stack = []
        r = root
        while r or stack:
            while r:
                stack.append(r)
                r = r.right
            r = stack.pop()
            self.total += r.val
            r.val = self.total
            r = r.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
'
运行
运行

---

【4】1022. 从根到叶的二进制数之和

考点： 递归 + 位运算

思路1： 递归，类似于前序遍历，当找到叶节点时对 sum 进行累加。

思路1： 递归求解，递归函数 dfs 的功能是查找累加目标数字并将其累加到全局变量 sum 中。递归结束边界为 root 为空，每碰到一个新的节点，就将其补在前面所得二进制数的末尾，具体实现为 “位运算（左移）+ 或操作”。当前节点为叶节点时，说明找到了要进行累加的数字，对全局变量 sum 进行累加，否则一直向下寻找。

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

class Solution:
    def __init__(self):
        self.sum = 0

    def sumRootToLeaf(self, root):

        def dfs(root, val):
            if not root: return
            newVal = val << 1 | root.val
            if not root.left and not root.right:
                self.sum += newVal
            else:
                dfs(root.left, newVal)
                dfs(root.right, newVal)

        mod = pow(10, 9) + 7
        dfs(root, 0)
        return self.sum % mod
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
'
运行
运行

---

【5】543. 二叉树的直径

考点：递归

思路1： 递归求树中每个节点的左右子树的高度，则该节点上的直径就是左右子树高度之和。设定全局变量 maxD，用于保存当前已知的树直径的最大值，递归返回值为左/右子树的较大者+1。递归边界条件为 root 为空时，树高度为 0。注意树的最大直径不一定过根节点（比如根节点的左右子树高度相差很大的情况），所以必须对树中每个节点的直接都进行判断，以获得最大值。时间复杂度：O(n)，二叉树中每个结点只被访问一次；空间复杂度：O(h)，h 为二叉树的高度，因为递归操作需要分配栈空间，最大栈空间就是递归的深度，即二叉树的高度。

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

class Solution:
    def __init__(self):
        self.maxD = 0
    def diameterOfBinaryTree(self, root):

        def depth(root):
            if not root: return 0
            left = depth(root.left)
            right = depth(root.right)
            d = left + right
            if d > self.maxD: self.maxD = d
            return max(left, right) + 1

        depth(root)
        return self.maxD
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
'
运行
运行

---

【6】563. 二叉树的坡度

考点：递归

思路： 每一个节点的坡度 = 左子树所有节点值之和 - 右子树所有节点值之和，那么只要递归地求每个节点左右子树的状态就可以了。再分析发现，自顶向下求会有很多重复计算，而自底向上求每个节点只需要访问一次。所以考虑递归地自底向上求解每个节点的坡度，以及每个节点与其左右子树节点值之和。而坡度 = |左子树和 - 右子树和|，所以递归的返回值就是每个节点与其子树节点值之和。

确定递归边界：root 为空时，返回和 = 0
确定递归返回值：当前节点值及其左右子树所有值之和

时间复杂度： O(n)，每个节点访问一次，共 n 个节点
空间复杂度： O(n)，当树倾斜时，n 个节点的树深度就是 n，此时递归栈需要保存 n 个状态

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

class Solution:
    def findTilt(self, root: TreeNode) -> int:
        def recur(root):
            if not root: return 0  # 递归边界
            left = recur(root.left)
            right = recur(root.right)
            self.tiltSum += abs(left - right)
            sumNode = left + right + root.val
            return sumNode  # 返回值为当前节点与其所有子节点的和

        self.tiltSum = 0
        recur(root)
        return self.tiltSum
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

---

【7】572. 另一个树的子树

考点：递归 / 字符串匹配

思路1： 将树的匹配作为递归问题，每遇到一个与目标子树根节点相同的节点，就向下进行递归匹配。
思路2： 将树的节点转换为顺序字符串，变成字符串匹配问题。

思路1： t 如果为 s 的子树，只可能发生在 s 树某个等于 t 树根节点的节点上。所以第一步就是遍历 s 树，找到等于 t 树根节点的节点，然后以此节点为出发向下判断是否和 t 的结构一致。

递归函数功能： 判断 s 树中以当前节点为根的树是否与 t 树一致
递归边界： 当 t 树和 s 树都遍历完成，指针均为空时返回 True；当 s/t 树已遍历完成，t/s 树未遍历完成，说明不匹配，返回 Fale；当 s 的值不等于 t 的值，说明不匹配，返回 False。
递归函数返回值： 左子节点是否匹配 and 右子节点是否匹配，均为 True 时则返回 True

时间复杂度： O(mn)，m 和 n 分别为 s 和 t 树的节点个数，最坏情况下每遍历到一个 s 树节点，就要调用 recur 递归判断，递归时间为 O(n)。
空间复杂度： O(m)，m 为 s 树的节点个数，最坏情况下 s、t 树退化为单链表。当 s 树节点个数 m 小于 t 树节点个数 n 时，s 树顶多全部遍历一遍就可以判断无法与 t 树匹配，递归调用栈大小为 m；当 s 树节点个数 m 大于 t 树节点个数时，最差情况遍历到 s 树倒数 m - n 个节点找到 t 树根，然后再进入递归 n 次判断是否匹配，实际上仍然是 m 个调用栈，或者是 s 到最后一个节点也没找到 t 的根，调用栈大小为 m。

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

class Solution:
    def isSubtree(self, s: TreeNode, t: TreeNode) -> bool:
        def recur(s, t):
            if not t and not s: return True
            if not t or not s or t.val != s.val: return False
            return recur(s.left, t.left) and recur(s.right, t.right)

        if not s or not t: return False
        res = recur(s, t) or self.isSubtree(s.left, t) or self.isSubtree(s.right, t)
        return res
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

思路2： 子树上的点在先序序列中是连续的，所以可以将两颗树都转换为先序序列，但目标树 t 的先序序列包含在 s 的先序序列中只是必要不充分条件，也就是包含不一定匹配，但不包含一定不匹配，因为空节点会导致顺序丢失。所以可以用 null 来补齐空节点的位置，这样一个先序序列就唯一地对应一棵树。

字符串匹配法：

• 暴力匹配：对于文本串 S 和 模式串 P，要判断 S 中是否有 P，循环比较两个字符串当前位置（i 和 j）字符是否一致，一致则 i++，j++，否则 j 归 0，i 从第一个匹配的位置的下一个位置重新开始检查匹配（即 i-j+1）。时间复杂度最坏情况下为O(mn)。
• KMP 算法：该算法关键是利用匹配失败后的信息，尽量减少模式串与主串的匹配次数以达到快速匹配的目的。具体就是实现一个 next() 函数，函数本身包含了模式串的局部匹配信息。时间复杂度为O(m+n)。
• Rabin-Karp 算法：把字符串看作是字符集长度进制的数，由数值的比较结果得出字符串的比较结果。

# 暴力匹配
class Solution:
    def isSubtree(self, s: TreeNode, t: TreeNode) -> bool:
        
        def dfs(root, sq):
            if not root: 
                sq.append('null')
                return
            sq.append(root.val)
            dfs(root.left, sq)
            dfs(root.right, sq)
            return sq

        s1, s2 = [], []   # 存储前序遍历序列
        ss = dfs(s, s1)
        ts = dfs(t, s2)
        i, j = 0, 0
        while i < len(ss) and j < len(ts):
            if ss[i] == ts[j]:
                i += 1
                j += 1
            else:
                i = i - j + 1
                j = 0
        if j == len(ts):
            return True
        return False
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

---

【8】606. 根据二叉树创建字符串

考点：递归

思路： 基本的前序遍历二叉树，只是改一改遍历过程中的操作。观察题目要求，可以发现有 4 种情况：

• 如果当前节点有左/右子树，则用括号“（）”进行包裹子树
• 如果当前节点没有左/右子树，则不做操作
• 如果当前节点只有左子树没有右子树，则只给左子树添加括号，不用给右子树进行任何操作
• 如果当前节点只有右子树没有左子树，为了保证二叉树顺序，需要为左子树添加一层“（）”表示为空，再对右子树递归

时间复杂度： O(n)，n 为二叉树节点数目
空间复杂度： O(n)，最坏情况下二叉树退化为单链表，需要 n 层调用栈空间

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

class Solution:
    def tree2str(self, t: TreeNode) -> str:
        if not t: return ""
        if not t.left and not t.right: return str(t.val)
        res = str(t.val)

        if t.left:
            res += '(' + self.tree2str(t.left) + ')'
        else:
            res += '()'
        if t.right:
            res += '(' + self.tree2str(t.right) + ')'
        return res
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

---

【9】617. 合并二叉树

考点：递归 & 二叉树的先序遍历

思路： 递归遍历 t1 和 t2，将 t2 和 t1 在同一位置上的节点值相加重新赋给 t1 的该位置。在遍历时会遇到 4 种情况：

• 当前遍历到的节点均不为空，直接相加赋值给 t1
• 其中一棵树为空，则用另一颗树的当前节点作为返回值
• 两棵树均为空，返回任意一棵树均可，都是空的

递归函数功能： 将 t1 与 t2 合并，并更新 t1
递归边界： 当 t1 或 t2 为空时，返回其中不为空的作为结果

时间复杂度： O(n)，n 为两棵树节点个数的较小值
空间复杂度： O(n)，二叉树退化为单链表，需要递归 n 层

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

class Solution:
    def mergeTrees(self, t1: TreeNode, t2: TreeNode) -> TreeNode:

        def dfs(t1, t2):
            if not t1: return t2
            if not t2: return t1
            t1.val += t2.val
            t1.left = dfs(t1.left, t2.left)
            t1.right = dfs(t1.right, t2.right)
            return t1

        if not t1 and not t2: return
        return dfs(t1, t2)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

---

【10】100. 相同的树

考点：递归

思路： 使用递归自顶向下判断两棵树是否完全相同，若当前节点相同，则继续向下判断左、右子树是否相同。

递归边界： 若当前节点在两个子树上都为空，则相同，返回 True；若当前节点只在一棵树为空，或者两棵树都不为空但值不同，直接返回 False。

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

class Solution:
    def isSameTree(self, p: TreeNode, q: TreeNode) -> bool:
        if not p and not q: return True
        if not p or not q or p.val != q.val: return False
        return self.isSameTree(p.left, q.left) and self.isSameTree(p.right, q.right)
1
2
3
4
5
6
7
8
9
10
11
12