难度: Medium
Submission
运行时间: 27 ms
内存: 17.5 MB
# 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 boundaryOfBinaryTree(self, root: Optional[TreeNode]) -> List[int]:
if not root:
return []
if not root.left and not root.right:
return [root.val]
def leftBoundary(root): # preorder
if not root or (not root.left and not root.right): # exclude leaf
return
res.append(root.val)
if root.left: # 如果有left substree, 描left as boundary
leftBoundary(root.left)
else: # if no substree, then use right as boundary
leftBoundary(root.right)
def rightBoundary(root): # postorder (so reversed order)
if not root or (not root.left and not root.right):
return
if root.right: # 如果有right substree, 描right as boundary
rightBoundary(root.right)
else:
rightBoundary(root.left)
res.append(root.val)
def leaves(node): # postorder
if not node:
return
if not node.left and not node.right:
res.append(node.val)
leaves(node.left)
leaves(node.right)
# eg 2
# step 0
res = [root.val] # [1]
# step 1: preorder to get the left boundary node value
leftBoundary(root.left) # [2] # must use root.left, otherwise will add root twice
# step 2: use dfs to find the leaves node value and append to the left boundary node value.
leaves(root) # [4, 7, 8, 9, 10]
# step 3: use postorder to find the right boundary and append to the previous node values.
rightBoundary(root.right) # [6, 3]
return res
"""
Gist: 二叉树的 边界 是由 根节点 、左边界 、按从左到右顺序的 叶节点 和 逆序的右边界 ，按顺序依次连接组成。
This question can be solved by Depth First Search.
This question applied various of knowledge of tree. To solve this question, we first use preorder to get the left boundary node value, then we use dfs to find the leaves node value and append to the left boundary node value. At last, we use postorder to find the right boundary and append to the previous node values.
https://zhenyu0519.github.io/2020/03/13/lc545/
"""
Explain
这个题目可以通过深度优先搜索（DFS）来解决。解题思路如下： 1. 先将根节点的值加入结果列表。 2. 通过先序遍历（preorder）得到左边界节点的值，并加入结果列表。注意要排除叶子节点。 3. 通过DFS找到所有叶子节点的值，按从左到右的顺序加入结果列表。 4. 通过后序遍历（postorder）得到右边界节点的值，并以逆序的方式加入结果列表。注意要排除叶子节点。
时间复杂度: O(n)
空间复杂度: O(n)
class Solution:
def boundaryOfBinaryTree(self, root: Optional[TreeNode]) -> List[int]:
if not root:
return []
if not root.left and not root.right:
return [root.val]
def leftBoundary(root): # 先序遍历得到左边界节点值
if not root or (not root.left and not root.right): # 排除叶子节点
return
res.append(root.val)
if root.left: # 如果有左子树，以左子树为边界
leftBoundary(root.left)
else: # 如果没有左子树，以右子树为边界
leftBoundary(root.right)
def rightBoundary(root): # 后序遍历得到右边界节点值（逆序）
if not root or (not root.left and not root.right): # 排除叶子节点
return
if root.right: # 如果有右子树，以右子树为边界
rightBoundary(root.right)
else: # 如果没有右子树，以左子树为边界
rightBoundary(root.left)
res.append(root.val)
def leaves(node): # DFS寻找所有叶子节点
if not node:
return
if not node.left and not node.right:
res.append(node.val)
leaves(node.left)
leaves(node.right)
res = [root.val] # 步骤1：加入根节点值
leftBoundary(root.left) # 步骤2：先序遍历得到左边界节点值
leaves(root) # 步骤3：DFS寻找叶子节点值，加入到结果列表
rightBoundary(root.right) # 步骤4：后序遍历得到右边界节点值，逆序加入结果列表
return res
Explore
在构造二叉树边界的过程中，如果在左边界和右边界中包含叶子节点，那么当这些叶子节点同时被计算为底部边界时，它们会在结果列表中被重复计算。为了避免这种重复，我们在左边界和右边界的计算中排除叶子节点，只在专门寻找叶子节点的步骤中将它们包括进来，确保每个节点在最终结果中只出现一次。
在左边界的定义中，一个没有左子树也没有右子树的节点即为叶子节点，因此在定义左边界时会跳过这样的节点。这种设计是故意的，以避免叶子节点在左边界或右边界中被重复计算。因此，这并不会漏掉边界条件，而是为了保持结果的一致性与准确性。
如果根节点只有一侧子树，处理逻辑会略有不同。例如，如果只有左子树而无右子树，左边界就是从根节点开始直到最左侧的路径，而右边界不存在。在这种情况下，右边界的递归函数不会有任何执行，因此只需要确保左边界和叶子节点正确收集。如果只有右子树，情况相反，需要正确处理右边界而忽略左边界。
在这种设计中，如果一个节点的一侧子树为null，选择遍历另一侧子树是为了确保边界的完整性。这种方法确保了在没有传统边界（如左子树或右子树）的情况下仍能尽可能地追踪边界。虽然这样做可能会导致边界看起来不是很直观（例如，边界可能包含了通常不认为是边界的节点），但这是为了保持边界的连续性，并确保所有外围的节点被考虑在内。