datetime:2024-01-16 14:48
author:nzb

二叉树

二叉树节点结构

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

class TreeNode {
public:
    int val;
    TreeNode* left;
    TreeNode* right;

    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

用递归和非递归两种方式实现二叉树的先序、中序、后序遍历

递归

最容易的方法

递归序

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right


def fn(head: TreeNode):
    # 1 第一次来到这个节点的时候
    if not head:
        return
    # 1 第一次来到这个节点的时候

    # 去递归该节点的左树
    fn(head.left)
    # 2 第二次来到这个节点的时候
    # 2 第二次来到这个节点的时候

    # 去递归该节点的右树
    fn(head.right)
    # 3 第三次来到这个节点的时候
    # 3 第三次来到这个节点的时候 
    # 到这才能确定这个节点结束了

#          1
#        /   \
#       2     3
#      / \   / \
#     4   5 6   7

# 按上面的流程，上树的递归序为
# 1 2 4 4 4 
# 2 5 5 5 2 
# 1 3 6 6 6 
# 3 7 7 7 3 1

# 递归方法每个节点都能回到3次，只是可能某一次啥也没做

先序遍历(左头右)->递归序第一次打印

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right


def tree_traverse(root: TreeNode):
    if root:
        print(root.val, end=" ")
        tree_traverse(root.left)
        tree_traverse(root.right)


# 示例：创建一个二叉树
#          1
#        /   \
#       2     3
#      / \   / \
#     4   5 6   7
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.left = TreeNode(4)
root.left.right = TreeNode(5)
root.right.left = TreeNode(6)
root.right.right = TreeNode(7)

# 打印可视化二叉树
tree_traverse(root)

中序遍历(头左右)->递归序第二次打印

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right


def tree_traverse(root: TreeNode):
    if root:
        tree_traverse(root.left)
        print(root.val, end=" ")
        tree_traverse(root.right)


# 示例：创建一个二叉树
#          1
#        /   \
#       2     3
#      / \   / \
#     4   5 6   7
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.left = TreeNode(4)
root.left.right = TreeNode(5)
root.right.left = TreeNode(6)
root.right.right = TreeNode(7)

# 打印可视化二叉树
tree_traverse(root)

后续遍历(左右头)->递归序第三次打印

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right


def tree_traverse(root: TreeNode):
    if root:
        tree_traverse(root.left)
        tree_traverse(root.right)
        print(root.val, end=" ")


# 示例：创建一个二叉树
#          1
#        /   \
#       2     3
#      / \   / \
#     4   5 6   7
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.left = TreeNode(4)
root.left.right = TreeNode(5)
root.right.left = TreeNode(6)
root.right.right = TreeNode(7)

# 打印可视化二叉树
tree_traverse(root)

非递归

递归是系统帮你压栈，非递归就是不让系统给你压栈

先序遍历

  • 准备一个栈
  • 把根节点压入栈
  • 步骤
    • 从栈中弹出一个节点记为cur
    • 打印或处理cur
    • 先压右再压左(如果有)，压的顺序右左，弹的顺序就是左右
    • 周而复始
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right


def pre_tree_traverse(root: TreeNode):
    if not root:
        return
    stack = [root]
    while stack:
        cur = stack.pop()
        print(cur.val, end=" ")
        if cur.right:
            stack.append(cur.right)
        if cur.left:
            stack.append(cur.left)


# 示例：创建一个二叉树
#          1
#        /   \
#       2     3
#      / \   / \
#     4   5 6   7
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.left = TreeNode(4)
root.left.right = TreeNode(5)
root.right.left = TreeNode(6)
root.right.right = TreeNode(7)

# 打印可视化二叉树
pre_tree_traverse(root)

中序遍历

  • 准备1个栈
  • 把根节点压入栈
  • 步骤
    • 每颗子树，整棵树左边界进栈
    • 依次弹出节点的过程中，打印并对弹出节点的右树重复以上步骤
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right


def in_tree_traverse(root: TreeNode):
    if not root:
        return
    stack = []
    while stack or root:
        if root:  # 不停的把左边界进栈
            stack.append(root)
            root = root.left
        else:  # 最后左边界走完了，为空，走该分支，弹出节点，打印，然后root指到右节点，然后又一直走左边界，即第一个分支
            cur = stack.pop()
            print(cur.val, end=" ")
            root = cur.right


# 为什么可以这样，因为整棵树可以被左边界(右边界)分解
# 1 2 4 是一个左边界
# 5 是一个左边界
# 3 6 是一个左边界
# 7 是一个左边界
# 把左边界放入栈，压的顺序头->左，弹出顺序左->头，一个节点弹出的时候让他的右树周而复始
# 左头右
#     |
#     v
#     左头右
#         |
#         v
#         左头右
#             |
#             v
#             左头右
#                 ...没有右的概念


# 示例：创建一个二叉树
#          1
#        /   \
#       2     3
#      / \   / \
#     4   5 6   7
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.left = TreeNode(4)
root.left.right = TreeNode(5)
root.right.left = TreeNode(6)
root.right.right = TreeNode(7)

# 打印可视化二叉树
in_tree_traverse(root)

后序遍历

前序遍历变化而来

  • 准备2个栈
  • 把根节点压入栈
  • 步骤
    • 从栈中弹出一个节点记为cur
    • 把cur放到收集栈里面
    • 先压左再压右(如果有)，压的顺序左右，弹的顺序就是右左，然后压入收集栈的顺序是右左，收集栈的弹出顺序是左右头(后序遍历)
    • 周而复始
  • 最后依次弹出收集栈的节点打印
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right


def post_tree_traverse(root: TreeNode):
    if not root:
        return
    stack = [root]
    stack_tmp = []
    while stack:
        cur = stack.pop()
        stack_tmp.append(cur)  # 不打印，压收集栈
        if cur.left:
            stack.append(cur.left)
        if cur.right:
            stack.append(cur.right)

    while stack_tmp:
        print(stack_tmp.pop().val, end=" ")


# 示例：创建一个二叉树
#          1
#        /   \
#       2     3
#      / \   / \
#     4   5 6   7
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.left = TreeNode(4)
root.left.right = TreeNode(5)
root.right.left = TreeNode(6)
root.right.right = TreeNode(7)

# 打印可视化二叉树
post_tree_traverse(root)

如何完成二叉树的深度优先遍历(就是先序遍历)

如何完成二叉树的宽度优先遍历(层序遍历)(常见题目：求一棵二叉树的宽度)

  • 宽度遍历用队列
  • 步骤
    • 头部进，尾部出
    • 弹出打印，先左再右
    • 周而复始
from collections import deque


class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right


def width_tree_traverse(root: TreeNode):
    if not root:
        return
    dq = deque([root])
    while dq:
        cur = dq.popleft()
        print(cur.val, end=" ")
        if cur.left:
            dq.append(cur.left)
        if cur.right:
            dq.append(cur.right)


# 示例：创建一个二叉树
#          1
#        /   \
#       2     3
#      / \   / \
#     4   5 6   7
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.left = TreeNode(4)
root.left.right = TreeNode(5)
root.right.left = TreeNode(6)
root.right.right = TreeNode(7)

# 打印可视化二叉树
width_tree_traverse(root)

求一棵二叉树的最大宽度


from collections import deque


class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right


def tree_width(root):
    if not root:
        return 0

    max_width = 0
    dq = deque([(root, 0)])  # 使用队列存储节点和节点在当前层的位置(索引)

    while dq:
        level_size = len(dq)  # 该层有多少节点
        _, level_start = dq[0]  # 开始位置，该层第一个节点的位置
        position = 0  # 结束位置
        for _ in range(level_size):  # 遍历该层节点，依次抛出
            node, position = dq.popleft()
            if node.left:
                dq.append((node.left, 2 * position))
            if node.right:
                dq.append((node.right, 2 * position + 1))

        max_width = max(max_width, position - level_start + 1)

    return max_width


# 利用队列进行层序遍历，队列中存储节点和节点在当前层的位置（这里用 position 表示）。
# 在每一层的遍历中，记录当前层的开始位置 level_start 和结束位置 position，计算当前层的宽度，并更新最大宽度 max_width。
# 将下一层的节点及其位置入队，节点位置的计算规则是左子节点为当前位置的2倍，右子节点为当前位置的2倍加1。
# 最终返回最大宽度。

#          1
#        /   \
#       2     3
#      / \   / \
#     4   5 6   7
# (1, 0)
# level_start = 0, position = 0, width = 1
# (2, 0)(3, 1)
# level_start = 0, 依次弹出后position = 1, width = 2
# (4, 0)(5, 1)(6, 2)(7, 3)
# level_start = 0, 依次弹出后position = 3, width = 4
# max_width = 4

#          1
#        /   \
#       2     3
#              \
#               7
# (1, 0)
# level_start = 0, position = 0, width = 1
# (2, 0)(3, 1)
# level_start = 0, 依次弹出后position = 1, width = 2
# (7, 3)
# level_start = 3, 依次弹出后position = 3, width = 1
# max_width = 2

# 示例：创建一个二叉树
#          1
#        /   \
#       2     3
#      / \   / \
#     4   5 6   7
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.left = TreeNode(4)
root.left.right = TreeNode(5)
root.right.left = TreeNode(6)
root.right.right = TreeNode(7)

# 打印可视化二叉树
print(tree_width(root))

如何判断一颗二叉树是否是搜索二叉树？

什么是搜索二叉树，就是对于一棵树来说，他的左树节点都比他小，右树节点都比他大

在标准的搜索二叉树中，节点值通常是唯一的，没有重复值的

#          5
#        /   \
#       3     7
#      / \   / \
#     2   4 6   8
#    /
#   1
  • 思路：用中序遍历，每次处理的时候看是否依次升序

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right


def is_bst(root: TreeNode):
    if not root:
        return True
    stack = []
    min_val = float("-inf")
    while stack or root:
        if root:
            stack.append(root)
            root = root.left
        else:
            cur = stack.pop()
            # 打印改成比较处理
            if cur.val > min_val:
                min_val = cur.val
            else:
                return False
            root = cur.right
    return True


# # 递归方法
# prev_val = float("-inf")
# 
# 
# def is_bst(root: TreeNode):
#     global prev_val
#     if not root:
#         return True
#     is_left_bst = is_bst(root.left)
#     if not is_left_bst:
#         return False
#     if root.val > prev_val:
#         prev_val = root.val
#     else:
#         return False
# 
#     return is_bst(root.right)


# 示例：创建一个二叉树
#          5
#        /   \
#       3     7
#      / \   / \
#     2   4 6   8
#    /
#   1
root = TreeNode(5)
root.left = TreeNode(3)
root.right = TreeNode(7)
root.left.left = TreeNode(2)
root.left.right = TreeNode(4)
root.right.left = TreeNode(6)
root.right.right = TreeNode(8)
root.left.left.left = TreeNode(1)
print(is_bst(root))
  • 递归套路

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right


def is_bst(root: TreeNode):
    if not root:
        # 空树是搜索二叉树，最小值和最大值都为空
        return True, float('inf'), float('-inf')

    # 递归判断左子树
    left_bst, left_min, left_max = is_bst(root.left)
    # 递归判断右子树
    right_bst, right_min, right_max = is_bst(root.right)
    # 判断当前节点是否满足搜索二叉树的性质
    current_bst = left_bst and right_bst and (left_max < root.val < right_min)
    # 更新当前子树的最小值和最大值
    # 递归的过程中，不断更新最小值和最大值，当当前节点子树作为上一级的左树或右树时，就需要返回最小值和最大值
    current_min = min(left_min, root.val)
    current_max = max(right_max, root.val)
    # 返回当前子树是否是搜索二叉树，最小值和最大值
    return current_bst, current_min, current_max


# # 版本二
# def is_bst(root: TreeNode, min_val=float("-inf"), max_val=float("inf")):
#     # base case (空树的返回)
#     if not root:
#         return True
# 
#     # 判断当前节点值是否在[min_val, max_val]的范围内
#     if not (min_val < root.val < max_val):
#         return False
#     # 递归判断左子树是否是BST（节点值范围更新为[min_val, root.val]）
#     left_bst = is_bst(root.left, min_val, root.val)
#     # 递归判断右子树是否是BST（节点值范围更新为[root.val, max_val]）
#     right_bst = is_bst(root.right, root.val, max_val)
#     # 返回当前树是否是BST
#     return left_bst and right_bst


# 创建一棵搜索二叉树:      2
#                     /   \
#                    1     3
root_bst = TreeNode(2)
root_bst.left = TreeNode(1)
root_bst.right = TreeNode(3)

print("是否是搜索二叉树:", is_bst(root_bst))  # 输出 True

# 创建一棵非搜索二叉树:      5
#                      /   \
#                     1     4
#                          / \
#                         3   6
root_non_bst = TreeNode(5)
root_non_bst.left = TreeNode(1)
root_non_bst.right = TreeNode(4, left=TreeNode(3), right=TreeNode(6))

print("是否是搜索二叉树:", is_bst(root_non_bst))  # 输出 False

如何判断一颗二叉树是完全二叉树？

什么是完全二叉树，之前的堆数据结构就是完全二叉树

每一层都满节点，即使是不满的最后一层，也是从左到右依次不满

  • 思路：二叉树按宽度遍历
    • 任意节点有右节点，没有左节点，直接返回false
    • 在第一个条件不违规的情况下，如果遇到了第一个左右节点不全的节点，那么接下来所有节点必须是叶子节点

from collections import deque


class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right


def is_cbt(root: TreeNode):
    if not root:
        return True
    dq = deque([root])
    leaf_flag = False
    while dq:
        cur = dq.popleft()
        # print(cur.val, end=" ")
        # 1、有右无左，不是
        # 2、或者孩子不全，之后的节点不是叶子节点，不是
        if (not cur.left and cur.right) or (leaf_flag and (cur.left or cur.right)):
            return False
        # 左右节点不全，后续应该都是叶子节点
        if not cur.left or not cur.right:
            leaf_flag = True

        if cur.left:
            dq.append(cur.left)
        if cur.right:
            dq.append(cur.right)

    return True


# 示例：创建一个二叉树
#            1
#        /       \
#       2         3
#      / \       / \
#     4   5     6   7
#    /\  / \    /
#   8  9 10 11  12
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.left = TreeNode(4)
root.left.right = TreeNode(5)
root.right.left = TreeNode(6)
root.right.right = TreeNode(7)
root.left.left.left = TreeNode(8)
root.left.left.right = TreeNode(9)
root.left.right.left = TreeNode(10)
root.left.right.right = TreeNode(11)
root.right.left.left = TreeNode(12)

print(is_cbt(root))

如何判断一颗二叉树是否是满二叉树？

  • 思路

    • 一个函数统计二叉树最大深度L
    • 一个函数统计二叉树节点个数N
    • 满二叉树满足N = 2 ** L - 1

  • 递归套路

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right


def is_full_tree(root: TreeNode):
    height, nodes = process(root)
    # 满二叉树节点数的计算方式
    return nodes == (1 << height) - 1  # 2 ** height - 1


def process(root: TreeNode):
    # base case(空树的返回)
    if not root:
        # 高度，节点数
        return 0, 0

    left_height, left_nodes = process(root.left)
    right_height, right_nodes = process(root.right)
    # 当前树的高度和节点个数
    height = max(left_height, right_height) + 1
    nodes = left_nodes + right_nodes + 1

    return height, nodes


# 创建一棵二叉树:      2
#                     /   \
#                    1     3
root_bst = TreeNode(2)
root_bst.left = TreeNode(1)
root_bst.right = TreeNode(3)

print("是否是满二叉树:", is_full_tree(root_bst))  # 输出 True

# 创建一棵非搜索二叉树:     5
#                      /   \
#                     1     4
#                          / \
#                         3   6
root_non_bst = TreeNode(5)
root_non_bst.left = TreeNode(1)
root_non_bst.right = TreeNode(4, left=TreeNode(3), right=TreeNode(6))

print("是否是满二叉树:", is_full_tree(root_non_bst))  # 输出 False

如何判断一颗二叉树是否是平衡二叉树？（二叉树题目套路）

平衡二叉树是指任何一颗子树来说，它左树的高度和它右树的高度差不能超过1


class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right


def is_balanced(root: TreeNode):
    # base case(空树的返回)
    if not root:
        return True, 0

    left_balanced, left_height = is_balanced(root.left)  # 递归计算左子树的平衡性和高度
    right_balanced, right_height = is_balanced(root.right)  # 递归计算右子树的平衡性和高度

    # 计算当前树的高度（取左右子树中较高的一个，并加上当前层）
    height = max(left_height, right_height) + 1
    # 判断当前树是否平衡（左右子树高度差不超过1，并且左右子树也分别是平衡的）
    is_balance = abs(left_height - right_height) < 2 and left_balanced and right_balanced

    return is_balance, height  # 返回当前树的平衡性和高度


# 创建一棵平衡二叉树:     1
#                     / \
#                    2   3
#                   / \
#                  4   5
root_balanced = TreeNode(1)
root_balanced.left = TreeNode(2, left=TreeNode(4), right=TreeNode(5))
root_balanced.right = TreeNode(3)

print("是否是平衡二叉树:", is_balanced(root_balanced))  # 输出 True

# 创建一棵非平衡二叉树:    1
#                      / \
#                     2   3
#                          \
#                           4
#                            \
#                             5
root_unbalanced = TreeNode(1)
root_unbalanced.left = TreeNode(2)
root_unbalanced.right = TreeNode(3)
root_unbalanced.right.right = TreeNode(4)
root_unbalanced.right.right.right = TreeNode(5)

print("是否是平衡二叉树:", is_balanced(root_unbalanced))  # 输出 False

二叉树递归套路(树形DP)

树形dp套路使用前提： 如果题目求解目标是S规则，则求解流程可以定成以每一个节点为头节点的子树在S规则下的每一个答案，并且最终答案一定在其中

  • 二叉树递归套路可以解决一切树形DP(树上做动态规划)，难度在于罗列可能性，可以向左树要信息，可以向右树要信息

  • 树形dp套路

    • 第一步： 以某个节点X为头节点的子树中，分析答案有哪些可能性，并且这种分析是以X的左子树、X的右子树和X整棵树的角度来考虑可能性的
    • 第二步： 根据第一步的可能性分析，列出所有需要的信息
    • 第三步： 合并第二步的信息，对左树和右树提出同样的要求，并写出信息结构
    • 第四步： 设计递归函数，递归函数是处理以X为头节点的情况下的答案。包括设计递归的basecase，默认直接得到左树和右树的所有信息，以及把可能性做整合，并且要返回第三步的信息结构这四个小步骤

树形DP的基本思想是，我们从叶子节点（底部）开始，计算和存储每个节点的状态，然后逐渐向上汇总这些状态，直到根节点，得到最终的解。这通常包括计算某种最优值、最长路径、最小代价等。

不能用该套路解的，比如求一棵树的中位数

  • 比如看一个是否是平衡二叉树，假设一颗子树X，可能性包括以下

    • X左树得是平衡二叉树
    • X右树也得是平衡二叉树
    • X 左树和右树的高度差不能超过1( <= 1)
    • 因此需要左右树的是否平衡和高度信息

  • 再比如看一棵树是否是搜索二叉树，满足以下

    • 左树是搜索二叉树
    • 右树是搜索二叉树
    • 左树的最大值小于当前节点值
    • 右树的最小值大于当前节点值
    • 需要(因为递归不能区分最大最小，因此都返回)
      • 左树：是否搜索二叉树，最大值
      • 右树：是否搜索二叉树，最小值
      • 返回值：是否搜索二叉树，最小值，最大值

二叉树节点间的最大距离问题

从二叉树的节点a出发，可以向上或者向下走，但沿途的节点只能经过一次，到达节点b时路径上的节点个数叫作a到b的距离，那么二叉树任何两个节点之间都有距离，求整棵树上的最大距离。

#                      1
#                     / \
#                    2   3
#                   / \
#                  4   5

比如4~5：3
比如4~3:4
  • 解题的一个常用标准：头结点参与不参与
  • 解题思路，考虑x(头结点)参与不参与，来罗列可能性
    • x不参与：左子树最大距离或右子树最大距离
    • x参与：左子树的高(离x最远) + 右子树的高 + 1(x自己)
    • 距离 = max(左子树最大距离, 右子树最大距离, 左子树的高 + 右子树的高 + 1)
    • 高度 = max(左子树的高, 右子树的高) + 1(x自己)
    • 需要的信息：最大距离和高度
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right


class Info:
    def __init__(self, dis, height):
        self.dis = dis
        self.height = height


def get_max_distance(head: TreeNode):
    if not head:  # base case
        return Info(0, 0)
    # 左右子树要信息
    left_info = get_max_distance(head.left)
    right_info = get_max_distance(head.right)
    # 信息整合
    can_yu = left_info.height + right_info.height + 1
    max_dis = max(left_info.dis, right_info.dis, can_yu)
    height = max(left_info.height, right_info.height) + 1
    return Info(max_dis, height)


#                      1
#                     / \
#                    2   3
#                   / \
#                  4   5
root = TreeNode(1)
root.left = TreeNode(2, left=TreeNode(4), right=TreeNode(5))
root.right = TreeNode(3)

print(get_max_distance(root).dis)

派对的最大快乐值

员工信息的定义如下:

class Employee {
  public int happy; // 这名员工可以带来的快乐值
  List<Employee> subordinates; // 这名员工有哪些直接下级
}

公司的每个员工都符合 Employee 类的描述。整个公司的人员结构可以看作是一棵标准的、没有环的多叉树。树的头节点是公司唯一的老板。除老板之外的每个员工都有唯一的直接上级。叶节点是没有任何下属的基层员工(subordinates列表为空) ，除基层员工外，每个员工都有一个或多个直接下级。这个公司现在要办party，你可以决定哪些员工来，哪些员工不来。但是要遵循如下规则。

  • 1.如果某个员工来了，那么这个员工的所有直接下级都不能来
  • 2.派对的整体快乐值是所有到场员工快乐值的累加
  • 3.你的目标是让派对的整体快乐值尽量大

给定一棵多叉树的头节点boss，请返回派对的最大快乐值。

        x
     /  |  \ 
    a   b   c
   /|\ /|\ /|\
  • 解题思路，列出可能性
    • x参与：x快乐值 + a整棵树在a不来的最大值 + b整棵树在b不来的最大值 + c整棵树在c不来的最大值
    • x不参与：0 + max(a来最大值, a不来的最大值) + max(b来的最大值, b不来的最大值) + max(c来的最大值, c不来的最大值)
    • 向每颗树要它来的最大值和不来的时候的最大值
class Employee:
    def __init__(self, happy, next_employees):
        self.happy = happy
        self.next_employees = next_employees


class Info:
    def __init__(self, come, no_come):
        self.come_max_happy = come
        self.no_come_max_happy = no_come


def get_max_happy(x: Employee):
    if not x.next_employees:  # base case, 基层员工
        return Info(x.happy, 0)
    lai = x.happy  # x来的情况下，整棵树的最大快乐值
    bu_lai = 0  # x不来的情况下，整棵树的最大快乐值
    for it in x.next_employees:
        next_info = get_max_happy(it)
        lai += next_info.no_come_max_happy
        bu_lai += max(next_info.come_max_happy, next_info.no_come_max_happy)  # x不来时，下级可以来也不来
    return Info(lai, bu_lai)


#                       10
#                     /  |  \
#                    3  20  40
#                   /   |   | \
#                  60   3   5  6

root = Employee(10, next_employees=[Employee(3, [Employee(60, [])]), Employee(20, [Employee(3, [])]),
                                    Employee(40, [Employee(5, []), Employee(6, [])])])

res = get_max_happy(root)
print(max(res.come_max_happy, res.no_come_max_happy))

给定两个二叉树的节点node1和node2，找到他们的最低公共祖先节点

  • 递归套路

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right


def lowest_common_ancestor(root: TreeNode, node1: TreeNode, node2: TreeNode):
    """LCA"""
    # 当前节点为空，返回空
    # 或者如果当前节点是其中之一，直接返回当前节点
    if not root or root == node1 or root == node2:  # base case
        return root

    left = lowest_common_ancestor(root.left, node1, node2)
    right = lowest_common_ancestor(root.right, node1, node2)

    # 节点1和节点2，不互为公共祖先的情况
    if left and right:
        return root
    # 如果只有左子树包含 node1 或 node2，则返回左子树的结果，否则返回右子树的结果
    # 叶子节点，返回空
    return left if left else right


# 创建一棵二叉树
#         3
#       /  \
#      5    1
#     / \  / \
#    6  2  0  8
#      / \
#     7   4
root = TreeNode(3)
root.left = TreeNode(5, left=TreeNode(6), right=TreeNode(2, left=TreeNode(7), right=TreeNode(4)))
root.right = TreeNode(1, left=TreeNode(0), right=TreeNode(8))

# 找到节点值为5和4的最低公共祖先
node1 = root.left  # 5
node2 = root.left.right.right  # 4
lca = lowest_common_ancestor(root, node1, node2)

if lca:
    print("节点 {} 和节点 {} 的最低公共祖先是节点 {}".format(node1.val, node2.val, lca.val))
else:
    print("找不到节点 {} 和节点 {} 的最低公共祖先".format(node1.val, node2.val))

# 找到节点值为5和8的最低公共祖先
node1 = root.left  # 5
node2 = root.right.right  # 8
lca = lowest_common_ancestor(root, node1, node2)

if lca:
    print("节点 {} 和节点 {} 的最低公共祖先是节点 {}".format(node1.val, node2.val, lca.val))
else:
    print("找不到节点 {} 和节点 {} 的最低公共祖先".format(node1.val, node2.val))
  • 剖析一下，一共两种情况
    • 情况一：节点1和节点2互为最低公共祖先
    • 情况二：节点1和节点2不互为最低公共祖先
# 创建一棵二叉树
#                   3  (左返回5，右返回空，所以公共祖先是5)
#      返回5      /    \
# (base case)   5      1  (子树返回空，返回空)
#              / \    / \
#             6  2   0   8 (0和8，左右节点都返回空，返回空)
#               / \
#              7   4
  • 情况一：节点5和节点4
    • 来到节点3，节点不等于空或5或4，base case跳过
      • 3向左树5要答案，来到5，满足base case, 返回5
      • 3向右树1要答案，来到1，不等于空或5或4，1继续向左右子树要答案，0和8，不等于空或5或4，各自都向子树要答案，左右子树都返回空，则一直往上返回空
      • 3的左返回5，右返回空，所以公共祖先是5(即函数的最后一行条件)
      • 意思就是，如果一颗子树既没有node1，也没有node2，一定会返回空
  • 情况二：节点6和节点4
# 创建一棵二叉树
#                             3  存在左节点，代码最后一行，因此返回5
#               返回5        /   \  (子树返回空，返回空)
#左右同时存在，返回当前节点5    5     1 
#             返回6        / \    返回4
#         (base case)     6   2   存在右节点，代码最后一行，因此返回4
#             返回空          / \   返回4
#                           7   4  (base case)

在二叉树中找到一个节点的后继节点

  • 后继节点：中序遍历得到一个序列，获取到对应节点的下一个节点
  • 前继节点：中序遍历得到一个序列，获取到对应节点的上一个节点
  • 时间复杂度O(N)

【题目】 现在有一种新的二叉树节点类型如下:

class Node:
    def __init__(self, value):
        self.value = value
        self.left = None
        self.right = None
        self.parent = None
  • 该结构比普通二叉树节点结构多了一个指向父节点的parent指针。
  • 假设有一棵Node类型的节点组成的二叉树，树中每个节点的parent指针都正确地指向自己的父节点，头节点的parent指向null。

  • 只给一个在二叉树中的某个节点node，请实现返回node的后继节点的函数，假设到后继节点k步，要去时间复杂度O(k)。

  • 思路

    • x有右树，则它右树的最左节点
    • x没有右树，一直往上看，看是不是它父节点的左节点，如果是，则父节点就是x的后继
    • 还需要考虑最右节点，它的后继节点为空

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right
        self.parent = None


def find_successor(node: TreeNode):
    if not node:
        return
    # 如果有右子树，则返回右子树的最左边的节点
    if node.right:
        return find_left_most(node.right)
    # 如果没有右子树，一直往上
    while node.parent:
        # 如果当前节点是父节点的左子树，则父节点即为后继节点
        if node.parent.left == node:
            return node.parent
        node = node.parent
    # 树中的最后一个节点，没有后继节点
    return None


def find_left_most(node: TreeNode):
    while node.left:
        node = node.left
    return node


# 创建节点
#         5
#       /   \
#      3     8
#     / \   / \
#    1   4 7   9


root = TreeNode(5)
root.left = TreeNode(3)
root.right = TreeNode(8)
root.left.left = TreeNode(1)
root.left.right = TreeNode(4)
root.right.left = TreeNode(7)
root.right.right = TreeNode(9)

# 设置父节点指针
root.left.parent = root
root.right.parent = root
root.left.left.parent = root.left
root.left.right.parent = root.left
root.right.left.parent = root.right
root.right.right.parent = root.right

successor_node = find_successor(root)  # 节点5

# 输出后继节点的值
if successor_node:
    print("后继节点的值:", successor_node.val)
else:
    print("节点3是树中的最后一个节点，没有后继节点。")

successor_node = find_successor(root.left.right)  # 节点4

# 输出后继节点的值
if successor_node:
    print("后继节点的值:", successor_node.val)
else:
    print("节点3是树中的最后一个节点，没有后继节点。")

successor_node = find_successor(root.right.right)  # 节点9

# 输出后继节点的值
if successor_node:
    print("后继节点的值:", successor_node.val)
else:
    print("节点3是树中的最后一个节点，没有后继节点。")

二叉树的序列化和反序列化

  • 就是内存里的一棵树如何变成字符串形式，又如何从字符串形式变成内存里的树
  • 可用先序遍历、中序遍历、后续遍历、层序遍历
  • 节点结束用_，空用#
         5
       /   \
     null    8
           /  \
          9   null
        /  \
      null  null
  • 先序遍历：5_#_8_9_#_#_#_

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right


def serializer(root: TreeNode):
    if not root:
        return "#_"
    serializer_res = str(root.val) + "_"
    serializer_res += serializer(root.left)
    serializer_res += serializer(root.right)
    return serializer_res


def deserializer(node_str: str):
    def build_tree(data: list):
        node_val = data.pop(0)
        if node_val == "#":
            return None
        node = TreeNode(int(node_val))
        node.left = build_tree(data)
        node.right = build_tree(data)
        return node

    node_data = node_str.split("_")
    return build_tree(node_data)


# 示例用法
# 创建一棵二叉树
#     5
#   /   \
# null    8
#       /  \
#      9   null
#    /  \
#  null  null
root = TreeNode(5)
root.right = TreeNode(8)
root.right.left = TreeNode(9)

# 序列化
serialized_tree = serializer(root)
print("序列化后的字符串:", serialized_tree)

# # 反序列化
deserialized_tree = deserializer(serialized_tree)

         5
       /   \
      8     null
    /  \     
  null  9
      /  \
   null   null
  • 先序遍历：5_8_#_9_#_#_#_

折纸问题

  • 请把一段纸条竖着放在桌子上，然后从纸条的下边向上方对折1次，压出折痕后展开。
  • 此时折痕是凹下去的，即折痕突起的方向指向纸条的背面。如果从纸条的下边向上方连续对折2次，压出折痕后展开，此时有三条折痕，从上到下依次是下折痕、下折痕和上折痕。
  • 给定一个输入参数N，代表纸条都从下边向上方连续对折N次。请从上到下打印所有折痕的方向。
  • 例如:N=1时，打印: down N=2时，打印: down down up

def print_all_folds(n: int):
    print_folds(1, n, True)  # 头结点是凹


def print_folds(n: int, depth: int, down: bool):
    """
    递归函数
    :param n: 第几层
    :param depth: 层数
    :param down:
        凹：down = True
        凸：down = False
    :return:
    """
    if n > depth:
        return
    print_folds(n + 1, depth, True)  # 左子树的头结点都是凹
    print("凹" if down else "凸", end=" ")
    print_folds(n + 1, depth, False)  # 右子树的头节点都是凸


# 创建节点
#         凹
#       /   \
#      凹     凸
#     / \   / \
#    凹  凸 凹   凸

print_all_folds(3)

results matching ""

    No results matching ""