Solutions CS101

Appearance

2 二叉树的遍历 16题 ​

sy329: 二叉树的先序遍历 ​

https://sunnywhy.com/sfbj/9/2/329

现有一棵个结点的二叉树（结点编号为从0到n-1，根结点为0号结点），求这棵二叉树的先序遍历序列。

输入

第一行一个整数 n(1≤n≤50)，表示二叉树的结点个数；

接下来行，每行一个结点，按顺序给出编号从0到n-1的结点的左子结点编号和右子结点编号，中间用空格隔开。如果不存在对应的子结点，那么用-1表示。

输出

输出个整数，表示先序遍历序列，中间用空格隔开，行末不允许有多余的空格。

样例1

输入

6
2 5
-1 -1
1 4
-1 -1
-1 -1
-1 3

输出

0 2 1 4 5 3

解释

对应的二叉树如下图所示，先序序列为0 2 1 4 5 3。

二叉树的先序遍历.png

python
from collections import deque

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

    def traversal(self, mode):
        result = []
        if mode == "preorder":
            result.append(self.val)
            if self.left is not None:
                result.extend(self.left.traversal(mode))
            if self.right is not None:
                result.extend(self.right.traversal(mode))
            return result
        elif mode == "postorder":
            if self.left is not None:
                result.extend(self.left.traversal(mode))
            if self.right is not None:
                result.extend(self.right.traversal(mode))
            result.append(self.val)
            return result
        elif mode == "inorder":
            if self.left is not None:
                result.extend(self.left.traversal(mode))
            result.append(self.val)
            if self.right is not None:
                result.extend(self.right.traversal(mode))
            return result
        elif mode == "levelorder":
            queue = deque([self])
            while queue:
                node = queue.popleft()
                result.append(node.val)
                if node.left:
                    queue.append(node.left)
                if node.right:
                    queue.append(node.right)
            return result
          
	def tree_height(self):
    if self is None:
        return -1  # 根据定义，空树高度为-1
    return max(tree_height(self.left), tree_height(self.right)) + 1


n = int(input())
nodes = [Node(i) for i in range(n)]
for i in range(n):
    left, right = map(int, input().split())
    nodes[i].left = nodes[left] if left != -1 else None
    nodes[i].right = nodes[right] if right != -1 else None

# "preorder", "postorder", "inorder, "levelorder"
mode = "levelorder"
pt = nodes[0]
result = pt.traversal(mode)

print(*result)

sy330: 二叉树的中序遍历 ​

https://sunnywhy.com/sfbj/9/2/330

mode = "preorder"

sy331: 二叉树的后序遍历 ​

https://sunnywhy.com/sfbj/9/2/331

mode = "postorder"

sy332: 二叉树的层次遍历 ​

https://sunnywhy.com/sfbj/9/2/332

mode = "levelorder"

python

sy333: 二叉树的高度 ​

https://sunnywhy.com/sfbj/9/2/333

层级 Level：从根节点开始到达一个节点的路径，所包含的边的数量，称为这个节点的层级。根节点的层级为 0。

高度 Height：树中所有节点的最大层级称为树的高度。因此空树的高度是-1。

python
from collections import deque

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

    def traversal(self, mode):
        result = []
        if mode == "preorder":
            result.append(self.val)
            if self.left is not None:
                result.extend(self.left.traversal(mode))
            if self.right is not None:
                result.extend(self.right.traversal(mode))
            return result
        elif mode == "postorder":
            if self.left is not None:
                result.extend(self.left.traversal(mode))
            if self.right is not None:
                result.extend(self.right.traversal(mode))
            result.append(self.val)
            return result
        elif mode == "inorder":
            if self.left is not None:
                result.extend(self.left.traversal(mode))
            result.append(self.val)
            if self.right is not None:
                result.extend(self.right.traversal(mode))
            return result
        elif mode == "levelorder":
            queue = deque([self])
            while queue:
                node = queue.popleft()
                result.append(node.val)
                if node.left:
                    queue.append(node.left)
                if node.right:
                    queue.append(node.right)
            return result

    def height(self):
        if self.left is None and self.right is None:
            return 0
        left_height = self.left.height() if self.left else 0
        right_height = self.right.height() if self.right else 0
        return max(left_height, right_height) + 1


n = int(input())
nodes = [Node(i) for i in range(n)]
has_parent = [False] * n  # 用来标记节点是否有父节点

for i in range(n):
    left, right = map(int, input().split())
    if left != -1:
        nodes[i].left = nodes[left]
        has_parent[left] = True
    if right != -1:
        nodes[i].right = nodes[right]
        has_parent[right] = True

# 寻找根节点，也就是没有父节点的节点
root_index = has_parent.index(False)
root = nodes[root_index]

# "preorder", "postorder", "inorder, "levelorder"
# mode = "levelorder"
# result = root.traversal(mode)
# print(*result)

"""
6
2 5
-1 -1
1 4
-1 -1
-1 -1
-1 3
"""
print(root.height())
# 2

sy334: 二叉树的结点层号 ​

https://sunnywhy.com/sfbj/9/2/334

现有一棵个结点的二叉树（结点编号为从0到n-1，根结点为0号结点），求这棵二叉树所有结点的层号（假设根结点的层号为1）。

输入

第一行一个整数 n (1<=n<=50)，表示二叉树的结点个数；

接下来行，每行一个结点，按顺序给出编号从0到n-1的结点的左子结点编号和右子结点编号，中间用空格隔开。如果不存在对应的子结点，那么用-1表示。

输出

输出个整数，分别表示编号从0到n-1的结点的层号，中间用空格隔开，行末不允许有多余的空格。

样例1

输入

6
2 5
-1 -1
1 4
-1 -1
-1 -1
-1 3

输出

1 3 2 3 3 2

解释

对应的二叉树如下图所示，层号为1的结点编号为0，层号为2的结点编号为2、5，层号为3的结点编号为1、4、3。

二叉树的先序遍历.png

python
from collections import deque

def node_levels(n, nodes):
    levels = [0] * n
    queue = deque([(0, 1)])  # (node, level)

    while queue:
        node, level = queue.popleft()
        levels[node] = level
        left, right = nodes[node]
        if left != -1:
            queue.append((left, level + 1))
        if right != -1:
            queue.append((right, level + 1))

    return levels

n = int(input())
nodes = [[left, right] for left, right in [map(int, input().split()) for _ in range(n)]]

print(*node_levels(n, nodes))

sy335: 翻转二叉树 ​

https://sunnywhy.com/sfbj/9/2/335

现有一棵个结点的二叉树（结点编号为从0到n-1，根结点为0号结点），将这棵二叉树中每个结点的左右子树交换，输出新的二叉树的先序序列和中序序列。

输入

第一行一个整数 n (1<=n<=50)，表示二叉树的结点个数；

接下来行，每行一个结点，按顺序给出编号从0到n-1的结点的左子结点编号和右子结点编号，中间用空格隔开。如果不存在对应的子结点，那么用-1表示。

输出

输出两行，第一行为先序序列，第二行为中序序列。整数之间用空格隔开，行末不允许有多余的空格。

样例1

输入

6
2 5
-1 -1
1 4
-1 -1
-1 -1
-1 3

输出

0 5 3 2 4 1
3 5 0 4 2 1

解释

对应的二叉树和翻转后的二叉树如下图所示。

翻转二叉树.png

python
class Node():
    def __init__(self, val, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def flip_tree(node):
    if node is None:
        return
    node.left, node.right = node.right, node.left
    flip_tree(node.left)
    flip_tree(node.right)

def preorder_traversal(node):
    if node is None:
        return []
    return [node.val] + preorder_traversal(node.left) + preorder_traversal(node.right)

def inorder_traversal(node):
    if node is None:
        return []
    return inorder_traversal(node.left) + [node.val] + inorder_traversal(node.right)

n = int(input())
nodes = [Node(i) for i in range(n)]
for i in range(n):
    left, right = map(int, input().split())
    nodes[i].left = nodes[left] if left != -1 else None
    nodes[i].right = nodes[right] if right != -1 else None

flip_tree(nodes[0])

print(*preorder_traversal(nodes[0]))
print(*inorder_traversal(nodes[0]))

sy336: 先序中序还原二叉树 ​

https://sunnywhy.com/sfbj/9/2/336

现有一棵个结点的二叉树（结点编号为从0到n-1），已知其先序序列和中序序列，求后序序列。

输入

第一行一个整数 n (1<=n<=50)，表示二叉树的结点个数；

第二行为个整数，表示二叉树的先序序列；

第三行为个整数，表示二叉树的中序序列。

输出

输出个整数，表示二叉树的后序序列，中间用空格隔开，行末不允许有多余的空格。

样例1

输入

6
0 2 1 4 5 3
1 2 4 0 5 3

输出

1 4 2 3 5 0

解释

对应的二叉树如下图所示，其后序序列为1 4 2 3 5 0。

二叉树的先序遍历.png

python
class Node():
    def __init__(self, val, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def build_tree(preorder, inorder):
    if inorder:
        index = inorder.index(preorder.pop(0))
        node = Node(inorder[index])
        node.left = build_tree(preorder, inorder[0:index])
        node.right = build_tree(preorder, inorder[index+1:])
        return node

def postorder_traversal(node):
    if node is None:
        return []
    return postorder_traversal(node.left) + postorder_traversal(node.right) + [node.val]

n = int(input())
preorder = list(map(int, input().split()))
inorder = list(map(int, input().split()))

root = build_tree(preorder, inorder)
print(*postorder_traversal(root))

sy337: 后序中序还原二叉树 ​

https://sunnywhy.com/sfbj/9/2/337

现有一棵个结点的二叉树（结点编号为从0到n-1），已知其后序序列和中序序列，求先序序列。

输入

第一行一个整数 n (1<=n<=50)，表示二叉树的结点个数；

第二行为个整数，表示二叉树的后序序列；

第三行为个整数，表示二叉树的中序序列。

输出

输出个整数，表示二叉树的先序序列，中间用空格隔开，行末不允许有多余的空格。

样例1

输入

6
1 4 2 3 5 0
1 2 4 0 5 3

输出

0 2 1 4 5 3

解释

对应的二叉树如下图所示，其先序序列为0 2 1 4 5 3。

二叉树的先序遍历.png

python
class Node():
    def __init__(self, val, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def build_tree(postorder, inorder):
    if inorder:
        index = inorder.index(postorder.pop())
        node = Node(inorder[index])
        node.right = build_tree(postorder, inorder[index+1:])
        node.left = build_tree(postorder, inorder[0:index])
        return node

def preorder_traversal(node):
    if node is None:
        return []
    return [node.val] + preorder_traversal(node.left) + preorder_traversal(node.right)

n = int(input())
postorder = list(map(int, input().split()))
inorder = list(map(int, input().split()))

root = build_tree(postorder, inorder)
print(*preorder_traversal(root))

sy338: 层序中序还原二叉树 ​

https://sunnywhy.com/sfbj/9/2/338

现有一棵个结点的二叉树（结点编号为从0到n-1），已知其层序序列和中序序列，求先序序列。

输入

第一行一个整数n (1<=n<=50)，表示二叉树的结点个数；

第二行为个整数，表示二叉树的层序序列；

第三行为个整数，表示二叉树的中序序列。

输出

输出个整数，表示二叉树的先序序列，中间用空格隔开，行末不允许有多余的空格。

样例1

输入

6
0 2 5 1 4 3
1 2 4 0 5 3

输出

0 2 1 4 5 3

解释

对应的二叉树如下图所示，其先序序列为0 2 1 4 5 3。

二叉树的先序遍历.png

python
class Node():
    def __init__(self, val, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def build_tree(levelorder, inorder):
    if inorder:
        for i in range(0, len(levelorder)):
            if levelorder[i] in inorder:
                node = Node(levelorder[i])
                io_index = inorder.index(levelorder[i])
                break
        node.left = build_tree(levelorder, inorder[0:io_index])
        node.right = build_tree(levelorder, inorder[io_index+1:])
        return node

def preorder_traversal(node):
    if node is None:
        return []
    return [node.val] + preorder_traversal(node.left) + preorder_traversal(node.right)

n = int(input())
levelorder = list(map(int, input().split()))
inorder = list(map(int, input().split()))

root = build_tree(levelorder, inorder)
print(*preorder_traversal(root))

sy339: 二叉树的最近公共祖先 ​

https://sunnywhy.com/sfbj/9/2/339

现有一棵个结点的二叉树（结点编号为从0到n-1，根结点为0号结点），求两个指定编号结点的最近公共祖先。

注：二叉树上两个结点A、B的最近公共祖先是指：二叉树上存在的一个结点，使得既是的祖先，又是的祖先，并且需要离根结点尽可能远（即层号尽可能大）。

输入

第一行三个整数n、k1、k2(1≤n≤50,0≤k1≤n−1,0≤k2≤n−1)，分别表示二叉树的结点个数、需要求最近公共祖先的两个结点的编号；

接下来行，每行一个结点，按顺序给出编号从0到n-1的结点的左子结点编号和右子结点编号，中间用空格隔开。如果不存在对应的子结点，那么用-1表示。

输出

输出一个整数，表示最近公共祖先的编号。

样例1

输入

6 1 4
2 5
-1 -1
1 4
-1 -1
-1 -1
-1 3

输出

2

解释

对应的二叉树如下图所示，结点1和结点4的公共祖先有结点2和结点0，其中结点2是最近公共祖先。

二叉树的先序遍历.png

python
class Node():
    def __init__(self, val, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def find_path(root, path, k):
    if root is None:
        return False
    path.append(root.val)
    if root.val == k:
        return True
    if ((root.left != None and find_path(root.left, path, k)) or
            (root.right!= None and find_path(root.right, path, k))):
        return True
    path.pop()
    return False

def find_LCA(root, n1, n2):
    path1 = []
    path2 = []
    if (not find_path(root, path1, n1) or not find_path(root, path2, n2)):
        return -1
    i = 0
    while(i < len(path1) and i < len(path2)):
        if path1[i] != path2[i]:
            break
        i += 1
    return path1[i-1]

n, n1, n2 = map(int, input().split())
nodes = [Node(i) for i in range(n)]
for i in range(n):
    left, right = map(int, input().split())
    nodes[i].left = nodes[left] if left != -1 else None
    nodes[i].right = nodes[right] if right != -1 else None

print(find_LCA(nodes[0], n1, n2))

sy340: 二叉树的路径和 ​

https://sunnywhy.com/sfbj/9/2/340

现有一棵个结点的二叉树（结点编号为从0到n-1，根结点为0号结点），每个结点有各自的权值。

  1. 结点的路径和是指，从根结点到该结点的路径上所有结点的权值之和；
  2. 二叉树的路径和是指，二叉树所有叶结点的路径和之和。

求这棵二叉树的路径和。

输入

第一行一个整数n (1<=n<=50)，表示二叉树的结点个数；

第二行个整数，分别给出编号从0到n-1的个结点的权值（）；

接下来行，每行一个结点，按顺序给出编号从0到n-1的结点的左子结点编号和右子结点编号，中间用空格隔开。如果不存在对应的子结点，那么用-1表示。

输出

输出一个整数，表示二叉树的路径和。

样例1

输入

6
3 2 1 5 1 2
2 5
-1 -1
1 4
-1 -1
-1 -1
-1 3

输出

21

解释

对应的二叉树如下图所示，其中黑色数字为结点编号，编号右下角的灰色数字为结点权值。由此可得叶结点1的路径和为，叶结点4的路径和为，叶结点3的路径和为，因此二叉树的路径和为。

二叉树的路径和.png

python
class Node():
    def __init__(self, val, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def path_sum(node, current_sum=0):
    if node is None:
        return 0
    current_sum += node.val
    if node.left is None and node.right is None:
        return current_sum
    return path_sum(node.left, current_sum) + path_sum(node.right, current_sum)

n = int(input())
values = list(map(int, input().split()))
nodes = [Node(values[i]) for i in range(n)]
for i in range(n):
    left, right = map(int, input().split())
    nodes[i].left = nodes[left] if left != -1 else None
    nodes[i].right = nodes[right] if right != -1 else None

print(path_sum(nodes[0]))

sy341: 二叉树的带权路径长度 ​

https://sunnywhy.com/sfbj/9/2/341

现有一棵个结点的二叉树（结点编号为从0到n-1，根结点为0号结点），每个结点有各自的权值。

  1. 结点的路径长度是指，从根结点到该结点的边数；
  2. 结点的带权路径长度是指，结点权值乘以结点的路径长度；
  3. 二叉树的带权路径长度是指，二叉树所有叶结点的带权路径长度之和。

求这棵二叉树的带权路径长度。

输入

第一行一个整数 n (1<=n<=50)，表示二叉树的结点个数；

第二行个整数，分别给出编号从0到n-1的个结点的权值（）；

接下来行，每行一个结点，按顺序给出编号从0到n-1的结点的左子结点编号和右子结点编号，中间用空格隔开。如果不存在对应的子结点，那么用-1表示。

输出

输出一个整数，表示二叉树的带权路径长度。

样例1

输入

5
2 3 1 2 1
2 3
-1 -1
1 4
-1 -1
-1 -1

输出

10

解释

对应的二叉树如下图所示，其中黑色数字为结点编号，编号右下角的格式为结点权值*结点路径长度=结点带权路径长度。由此可得二叉树的带权路径长度为。

二叉树的带权路径长度.png

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

def build_tree(weights, edges):
    # 根据边构建二叉树，并返回根节点
    nodes = [TreeNode(w) for w in weights]
    for i, (left, right) in enumerate(edges):
        if left != -1:
            nodes[i].left = nodes[left]
        if right != -1:
            nodes[i].right = nodes[right]
    return nodes[0] if nodes else None

def weighted_path_length(node, depth=0):
    # 计算带权路径长度
    if not node:
        return 0
    # 如果是叶子节点，返回其带权路径长度
    if not node.left and not node.right:
        return node.value * depth
    # 否则递归计算左右子树的带权路径长度
    return weighted_path_length(node.left, depth + 1) + weighted_path_length(node.right, depth + 1)

# 输入处理
n = int(input())  # 节点个数
weights = list(map(int, input().split()))  # 各节点权值
edges = [list(map(int, input().split())) for _ in range(n)]  # 节点边

# 构建二叉树
root = build_tree(weights, edges)

# 计算并输出带权路径长度
print(weighted_path_length(root))

sy342: 二叉树的左视图序列 ​

https://sunnywhy.com/sfbj/9/2/342

现有一棵个结点的二叉树（结点编号为从0到n-1，根结点为0号结点），从二叉树的左侧看去，同一层的多个结点只能看到这层中最左边的结点，这些能看到的结点从上到下组成的序列称为左视图序列。求这棵二叉树的左视图序列。

输入

第一行一个整数 n (1<=n<=50)，表示二叉树的结点个数；

接下来行，每行一个结点，按顺序给出编号从0到n-1的结点的左子结点编号和右子结点编号，中间用空格隔开。如果不存在对应的子结点，那么用-1表示。

输出

输出若干个整数，表示左视图序列，中间用空格隔开，行末不允许有多余的空格。

样例1

输入

6
2 5
-1 -1
1 4
-1 -1
-1 -1
-1 3

输出

0 2 1

解释

对应的二叉树如下图所示，从左侧看去，第一层可以看到结点0，第二层可以看到结点2，第三层可以看到结点1，因此左视图序列是0 2 1。

二叉树的先序遍历.png

python
class Node():
    def __init__(self, val, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def left_view(root):
    if root is None:
        return []
    queue = [root]
    view = [root.val]
    while queue:
        level = []
        for node in queue:
            if node.left:
                level.append(node.left)
            if node.right:
                level.append(node.right)
        if level:
            view.append(level[0].val)
        queue = level
    return view

n = int(input())
nodes = [Node(i) for i in range(n)]
for i in range(n):
    left, right = map(int, input().split())
    nodes[i].left = nodes[left] if left != -1 else None
    nodes[i].right = nodes[right] if right != -1 else None

print(*left_view(nodes[0]))

sy343: 满二叉树的判定 ​

https://sunnywhy.com/sfbj/9/2/343

现有一棵个结点的二叉树（结点编号为从0到n-1，根结点为0号结点），判断这个二叉树是否是满二叉树。

注：如果一棵二叉树每一层的结点数都达到了当层能达到的最大结点数（即如果二叉树的层数为，且结点总数为 2k−1），那么称这棵二叉树为满二叉树。

输入

第一行一个整数n (1<=n<=64)，表示二叉树的结点个数；

接下来行，每行一个结点，按顺序给出编号从0到n-1的结点的左子结点编号和右子结点编号，中间用空格隔开。如果不存在对应的子结点，那么用-1表示。

输出

如果是满二叉树，那么输出Yes，否则输出No。

样例1

输入

7
2 5
-1 -1
1 4
-1 -1
-1 -1
6 3
-1 -1

输出

Yes

解释

对应的二叉树如下图所示，是满二叉树。

满二叉树的判定.png

python
class Node():
    def __init__(self, val, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def is_full(node):
    if node is None:
        return True
    if (node.left is None and node.right is None) or (node.left is not None and node.right is not None):
        return is_full(node.left) and is_full(node.right)
    return False

n = int(input())
nodes = [Node(i) for i in range(n)]
for i in range(n):
    left, right = map(int, input().split())
    nodes[i].left = nodes[left] if left != -1 else None
    nodes[i].right = nodes[right] if right != -1 else None

print("Yes" if is_full(nodes[0]) else "No")

sy344: 完全二叉树的判定 ​

https://sunnywhy.com/sfbj/9/2/344

现有一棵个结点的二叉树（结点编号为从0到n-1，根结点为0号结点），判断这个二叉树是否是完全二叉树。

注：如果一棵二叉树除了最下面一层之外，其余层的结点个数都达到了当层能达到的最大结点数，且最下面一层只从左至右连续存在若干结点，而这些连续结点右边不存在别的结点，那么就称这棵二叉树为完全二叉树。

输入

第一行一个整数n (1<=n<=64)，表示二叉树的结点个数；

接下来行，每行一个结点，按顺序给出编号从0到n-1的结点的左子结点编号和右子结点编号，中间用空格隔开。如果不存在对应的子结点，那么用-1表示。

输出

如果是完全二叉树，那么输出Yes，否则输出No。

样例1

输入

6
2 5
-1 -1
1 4
-1 -1
-1 -1
3 -1

输出

Yes

解释

对应的二叉树如下图所示，是完全二叉树。

完全二叉树的判定.png

python
class Node():
    def __init__(self, val, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def is_complete(root):
    if root is None:
        return True
    queue = [root]
    flag = False
    while queue:
        node = queue.pop(0)
        if node.left:
            if flag:  # If we have seen a node with a missing right or left child
                return False
            queue.append(node.left)
        else:
            flag = True
        if node.right:
            if flag:  # If we have seen a node with a missing right or left child
                return False
            queue.append(node.right)
        else:
            flag = True
    return True

n = int(input())
nodes = [Node(i) for i in range(n)]
for i in range(n):
    left, right = map(int, input().split())
    nodes[i].left = nodes[left] if left != -1 else None
    nodes[i].right = nodes[right] if right != -1 else None

print("Yes" if is_complete(nodes[0]) else "No")