跳转至

LeetCode: 545. 二叉树的边界

1、题目描述

给定一棵二叉树,以**逆时针**顺序从根开始返回其边界。边界按顺序包括左边界、叶子结点和右边界而不包括重复的**结点**。 (结点的值可能重复)

**左边界**的定义是从根到**最左侧**结点的路径。**右边界**的定义是从根到**最右侧**结点的路径。若根没有左子树或右子树,则根自身就是左边界或右边界。注意该定义只对输入的二叉树有效,而对子树无效。

**最左侧**结点的定义是:在左子树存在时总是优先访问,如果不存在左子树则访问右子树。重复以上操作,首先抵达的结点就是最左侧结点。

最右侧结点的定义方式相同,只是将左替换成右。

示例 1

输入:
  1
   \
    2
   / \
  3   4

输出:
[1, 3, 4, 2]

解析:
根不存在左子树,故根自身即为左边界。
叶子结点是3和4。
右边界是1,2,4。注意逆时针顺序输出需要你输出时调整右边界顺序。
以逆时针顺序无重复地排列边界,得到答案[1,3,4,2]。

示例 2

输入:
    ____1_____
   /          \
  2            3
 / \          / 
4   5        6   
   / \      / \
  7   8    9  10  

输出:
[1,2,4,7,8,9,10,6,3]

解析:
左边界是结点1,2,4。(根据定义,4是最左侧结点)
叶子结点是结点4,7,8,9,10。
右边界是结点1,3,6,10。(10是最右侧结点)
以逆时针顺序无重复地排列边界,得到答案 [1,2,4,7,8,9,10,6,3]。

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 boundaryOfBinaryTree(self, root: TreeNode) -> List[int]:
        if not root:
            return []
        if not root.left and not root.right:
            return [root.val]

        left_edge = []
        leaf_node = []
        right_edge = []

        def get_left_edge(node):
            if not node:
                return
            if node.left:
                left_edge.append(node.val)
                get_left_edge(node.left)
            elif node.right:
                left_edge.append(node.val)
                get_left_edge(node.right)

        def get_leaf_node(node):
            if not node:
                return
            if not node.left and not node.right:
                leaf_node.append(node.val)
                return
            if node.left:
                get_leaf_node(node.left)
            if node.right:
                get_leaf_node(node.right)

        def get_right_edge(node):
            if not node:
                return
            if node.right:
                right_edge.append(node.val)
                get_right_edge(node.right)
            elif node.left:
                right_edge.append(node.val)
                get_right_edge(node.left)

        get_left_edge(root.left)
        get_right_edge(root.right)
        get_leaf_node(root)
        return [root.val] + left_edge + leaf_node + list(reversed(right_edge))