算法笔记-树

Algorithm › Data Structure › Tree

Conclusion

与树结构相关的题，多为递归求解。 若可确定使用递归求解树相关的题， 则：

  • 分析问题， 确定解体步骤。
  • 按照步骤，确定递归函数。 所谓确定递归函数，即以下三个步骤：
    • 确定函数终止条件
      • 在利用递归解决树相关问题时， 为了确定函数终止条件， 可以从输入的节点的不同状态入手，进而判断何时应该是False, 也即被拦截，或者说被终止。例如， a, b两个节点都为空则如何， 一个为空如何等等。 同时，如果有可以合并的终止条件， 那么在写if 条件时， 可以利用不同 if 间的顺序达到精简代码的效果。
      • 并且目前接触到的大部分情况下。 再树中递归时的终止条件基本是拦截所有False的情况， 对于True的情况不需显示写if拦截， 只需让程序继续往下跑即可。 那么通常此时是跑到 return的函数方程， 或者进行某些更改操作。
    • 确定函数功能
    • 确定递归方程
    • 切记不要用人脑模拟递归过程！

同时， 目前接触到的 “二叉树” 相关的需要递归的题， 要么是需要更改树， 要么是需要判断树是否满足某种条件，即只需遍历树的个节点值同时做判断，而非更改。

仅限目前接触的来说， 当需要更改树的内容时， 可”从下至上“ 更改。 那么在这种情况下，往往需要通过 前序遍历 先到达树的底部，然后进行更改操作， e.g. offer 26。 通常再这种情况下，代码的结构很可能是：

1
2
3
4
fun():
	pre_order_traversal(left)
    pre_order_traversal(right)
    do somthing..

**当不需要更改，只需要判断时， 可”从上至下判断”**。所为从上至下判断， 即每当一个节点进来递归函数， 先对该节点进行判断， 然后再 return fun(左) and fun(右)。e.g. offer 28。通常再这种情况下，代码的结构很可能是：

1
2
3
4
5
6
7
# 用if 过滤所有需被终止的不满足需求的条件。
if ...
	return 
if ...
	return 

return fun(left) and fun(right)

如果不想用递归， 那么可以使用栈实现， 因为只要能用递归求解的问题， 用栈都可解决， 递归的过程实际也就是计算机进行压栈出栈的过程。其典型代表即为BST的中/前序遍历。

二叉树

剑指offer 26. 判断输入的树B是否是A的子树。

思路：

  • 确定求解步骤 – 2步，对应两个递归函数：
    • 遍历树
    • 如果发现A中某节点与B的根节点相等， 则检查B的其他节点

注意：

  • 如果面试问到此题， 注意确认输入是否可以为空?， 如果可以的话， 空树是否是子树？

  • 体会下列代码中的终止条件判断

  • 此题的递归中过程可以理解成是自下向上在更改树

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
def is_subtree(a: Node, b: Node):
    """
    注意 check_subtree中的终止条件的写法和逻辑。
    再check_subtree中， 传入的两个参数状态一共五中：
    (1) a None b None: true
    (2) a None b not None: False
    (3) a not None b None: true
    (4) a not None b not None => equal: True, not equal: False


    :param a:  tree
    :param b:  subtree
    :return:
    """

    def check_subtree(a_root: Node, b_root: Node):

        # 能跑到b_root 是空， 则一定是subtree中的之前的节点已经相等了。所有此处为空的话则是b已经遍历完了，返回false
        # 如果这样无法理解， 那么就是 结合（1）（3） 发现，只要b是None， 不管a是不是None， 都为true
        if b_root is None:
            return True

        # 至此 b_root一定不为None， 也即b not None, a is None 的情况 --》 情况（2）
        if a_root is None:
            return False

        if a_root.value != b_root.value:
            return False

        # 至此 一定是状态(4)中的相等
        return check_subtree(a_root.right, b_root.right) and check_subtree(a_root.left, b_root.left)
	
    # 注意此处， 其中a is None的部分即是对于用户输入的检查，也是递归的终止条件。
    # 而 对b is None的判断则是单纯的用户输入检查
    if a is None or b is None:
        return False
	
    if a.value == b.value:
        if check_subtree(a, b):
            return True

    return is_subtree(a.left, b) or is_subtree(a.right, b)

剑指offer 28. 对称二叉树

思路：

  • 确定求解步骤 –1步，对应两个递归函数：
    • 遍历树, 同时检查两个节点的对称情况。

注意：

  • 注意对input为空值的判断。

  • 此题的递归中过程可以理解成是自上向下在判断树

  • 注意体会终止条件和recur 中的return； 

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
"""
    2021-12-6
    offer28

    对称二叉树。 一棵树如果与本身的镜像相同，则为对称二叉树。

    解法：
    实际上，要判断对称二叉树，新创建一个“对称前序遍历”的方法，将其结果与正常的前序遍历比较即可。

    但需包括结果中需包括空值， 例子看offer P178
"""


def is_symmetrical(root: Node):
    def recur(left, right):
        if left is None and right is not None:
            return False

        if right is None and left is not None:
            return False

        if left is None and right is None:
            return True

        if left.val != right.val:
            return False
		
        # 当程序运行到这， 说明两个节点的值是相等的，因为可能造成不对称的情况都已被上述终止条件拦截了
        # 那么只需继续判断两个当先节点下的子树是否对称即可
        # 而此处return的这种形式，可以经常被套用再从上至下遍历树的问题。
        return recur(left.right, right.left) and recur(left.left, right.right)

    if root is None:
        return True
    return recur(root.left, root.right)

二叉树 BF

二叉树的层级遍历1 leetcode102

该题提醒你： 面试写算法时 要问清输出格式。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
   3
   / \
  9  20
 /   /  \
0   15   7
返回其层序遍历结果：

[
  [3],
  [9,20],
  [0, 15,7]
]

注意， 是[0, 15, 7] 而不是 [[0], [15, 7]]

注意：
注意不可以利用”从上至下“ 的思路， 依次遍历每层中的每个node, 即按照如下错误代码的思路解题：**
该代码由你自己写于 2021-12-6， 这个代码的错误在于他的输出形式不符合要求， 即输出了上述”而不是“后面的格式

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
class Solution:
    def levelOrder(self, root: TreeNode) -> List[List[int]]:
        def traversal(node: TreeNode):
            if node is None:
                return
            temp = []

            if node.left is not None:
                temp.append(node.left.val)

            if node.right is not None:
                temp.append(node.right.val)

            if len(temp) != 0:
                result.append(temp)

            traversal(node.left)
            traversal(node.right)


        if root is None:
            return []

        result = [[root.val]]
        traversal(root)

正确定思路：
为每个层级标号， 即维护一个变量level记录当前再那一层， 然后直接把非空的值加入result中的level项。

实际上使用了深度有限的思想解决此题。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
def levelOrder(self, root):
    def traversal(node, level):
        if node is None:
            return
		# 如果当前层数为第一次到达， 再result中加入一个新的空列表
        if len(result) < level + 1:
            result.append([])
		
        # 按照level，再result中的level项加入值
        result[level].append(node.val)
        
        traversal(node.left, level + 1)
        traversal(node.right, level + 1)

    result = []
    traversal(root, 0)
    return result

二叉树层级遍历2

与上题不同， 该题的返回值是List[int] 而不是List[[]]， 故要用queue实现。

事实上，只要看到广度优先遍历的题，则应考虑是否可用queue实现。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
def levelOrder(root) -> List[int]:
    if root is None:
        return []

    result = []
    queue = collections.deque()
    queue.append(root)

    while len(queue) != 0:
        current_node = queue.popleft()
        result.append(current_node.val)
        if current_node.left is not None:
            queue.append(current_node.left)

        if current_node.right is not None:
            queue.append(current_node.right)

    return result

二叉树层级遍历3 （Z字形遍历） leetcode 剑指offer 32 - III

例如:
给定二叉树: [3,9,20,null,null,15,7],

​ 3

/
9 20
/
15 7
返回其层次遍历结果：

[
[3],
[20,9],
[15,7]
]

思路：

  • 由于对于不同层级的节点需要改变输出顺序， 故用单个队列无法实现
  • 改变思路为用两个栈实现
  • 一个栈对应奇数层的所有节点， 从右至左压入。 另一个对应偶数层，从左至右压入

注意理解：

  • 一个栈中的节点全部被弹出时，就代表该层已经遍历结束
  • 弹出后只需要：
    • append到temp
    • 将子节点压入另一个栈
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
from typing import List

from matplotlib import collections

from bst_review import Node


def levelOrder(root: Node) -> List[List[int]]:
    if root is None:
        return []

    result = []
    stack_push_from_left = []
    stack_push_from_right = [root]
    while len(stack_push_from_left) != 0 or len(stack_push_from_right) != 0:
        temp = []
        while len(stack_push_from_right) != 0:
            node = stack_push_from_right.pop(-1)
            temp.append(node.val)
            if node.left is not None:
                stack_push_from_left.append(node.left)
            if node.right is not None:
                stack_push_from_left.append(node.right)
        if temp:
            result.append(temp)
            temp = []

        while len(stack_push_from_left) != 0:
            node = stack_push_from_left.pop(-1)
            temp.append(node.val)
            if node.right is not None:
                stack_push_from_right.append(node.right)
            if node.left is not None:
                stack_push_from_right.append(node.left)
        if temp:
            result.append(temp)

    return result

平衡二叉树DF

后续遍历非递归

Overall Procedure:

  • 压左
  • 压左结束， 检查栈顶元素是否满足输出条件：
    • 栈顶元素应该被输出 –> 没有右子树， 或者右子树已经被输出过
    • 不应被输出 –> 右子树还为被压栈，也即还没被输出–> cur = cur.right循环压左。

关键：

  • 左-右-根
  • 只需记住点为：
    • 需维护一prev记录是否当前节点可以被记录至result。
    • 只有当 cur.right为空 或 cur.right == prev时 可以被输出， 此时做三件事。
      • pop stack
      • update prev
      • cur = None. 目的为实现循环，因为cur is None时不会进入第一个循环。
    • 不可以被输出则代表右侧子树还未被输出， 则只需 cur = cur.right即可实现循环。
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
def post_order_traversal_non_recursive(self):
    """
     2021-12-19
    :return:
    """
    cur = self.root
    stack = []
    result = []
    prev = self.root
    # 压至最左
    # 之所以加 cur is not None是为了最开始能进入循环
    # 因为stack初始为空， 不加这个条件进不来，同时也不能更改while cur is not None这个条件。
    while len(stack) != 0 or cur is not None:
        while cur is not None:
            stack.append(cur)
            cur = cur.left

        # 此处不弹出，而是检查
        cur = stack[-1]

        # 判断append到结果与否
        # 如果cur.right为空， 那么此时必然输出value，因为当程序到此处时， 已经压至最左
        # 如果cur.right不为空，但是cur.right == prev， 则代表当前节点的右侧子树已经全部输出，可以输出当前节点了。
        if cur.right is None or cur.right == prev:
            # 只要需要append结果： 则更新prev
            # 弹出stack
            # 使cur=None实现循环目的
            result.append(cur.value)
            stack.pop(-1)
            prev = cur
            cur = None
        else:
            # 如果不符合上列判断，则两种情况：
            # 当前节点的右子树还没有被输出， 则此时cur.right不为空， 会继续到第一个while压左
            # 或者当前节点的cur.right为空，即已经没有右子树， 则会略过第一个while， 继续检查输出与否
            cur = cur.right

    return result

中序遍历非递归

Overall Precedure:

  • 压左
  • pop， 只要pop就输出
  • 检查右子树是否存在， 存在则继续压左
  • 否则循环pop，方法为使cur = None

注意点：

  • 整体代码逻辑三个顺序遍历都一样。
  • 记住只要pop就输出即可。
  • 若是前序遍历， 则改成只要push就输出即可。
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
def inorderTraversal(self, root):
        """
        :type root: TreeNode
        :rtype: List[int]
        """
        cur = root
        stack = []
        result = []
        while len(stack) != 0 or cur is not None:
            # 压左
            while cur is not None:
                stack.append(cur)
                cur = cur.left
            
            # 至此， 一定是最左元素， 所以必pop，且只要pop就输出
            cur = stack.pop()
            result.append(cur.val)
            
            # pop过后检查右子树即可
            # 此处逻辑与后续遍历一样， 如果有右子树， 则循环使用第一个while
            # 无右子树， 则使cur=None就可略过第一个while， 继续pop
            if cur.right is not None:
                cur = cur.right
            else:
                cur = None
        
        return result

剑指offer33. 判断数组是否可以是后续遍历结果

Overall Precedure:

  • 只需记住一个数组若是BST的后序遍历结果， 那么最后一个元素必是根节点， 而之前的元素必是左+右。
  • 因此左子树中不能有大于root的元素
  • 右子树中不可有小于root的元素
  • 之后递归求解即可

注意：

  • 此题终止条件不是常规的在函数起点直接if判断。
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
def check_back_order_traversal(nums):
    """
    2021-12-19
    思路：
    判断树的后序遍历， 则首先需明确其特点：
    数组最后一位必为根节点。 那么根节点之前的elements， 必为左右子树， 且左右子树连续， 即必一组都小于root的+一组都大于root的
    e.g. [5, 7, 6, 9, 11, 10, 8] --> root = 8; left = [5, 7, 6]; right = [9, 11, 10, 8]
    那么此时， 继续判断left和right是否符合条件即可。 上例中， 如果right = [9, 1, 11, 10, 8]则不符条件， 因为右子树中无小于root
    的元素

    至此， 可确定必为使用递归解决。

    递归：
        递归函数作用：
            判断当前列表是否符合后续遍历条件
        函数方程：
            left and right 则True
        函数终止条件：
            当list长度小于等于2， 则必为True；
            当右子树中出现比root小的元素， 则为false；

        此题特殊点在于终止条件不是简单的写于前面的if， 而是先找到左右子树， 再判断右子树是否符合。
        之所以说只需判断右子树， 是因为第一while中的左子树一定是符合条件的。 因为找到的元素都是小于root的。
    :param nums:
    :return:
    """
    def recursive(nums):
        if len(nums) <= 2:
            return True

        root = nums[-1]
        left_end = 0
        while left_end < len(nums) and nums[left_end] < root:
            # 此处注意， [5, 7, 6, 9, 11, 10, 8]中， 第一次遍历时实际left_end应该等于2, 但是这里是等于3的， 因为Left_end先
            # 加了1才判断不符合while条件。 所以再return中切片时， 切成[0: left_end]正好符合所需。
            left_end += 1

        for i in range(left_end, len(nums)):
            if nums[i] < root:
                return False
        # 注意and后的切片范围不要弄错，传入下一个递归中的数组不要带上当前root。
        return recursive(nums[0:left_end]) and recursive(nums[left_end:len(nums)-1])

    if len(nums) == 0:
        return True

    return recursive(nums)

Created by Shain at 2021/12/06, Mel, Australia

Last Updated: 2021/12/19