ARTS Week 32_什么是树的边界

ARTS Week 32

当你走出家乡的时候，你就是你自己的家乡

---

Algoithm

二叉树的边界

概述

二叉树的 边界 是由 根节点 、左边界 、按从左到右顺序的 叶节点 和 逆序的右边界 ，按顺序依次连接组成。

左边界 是满足下述定义的节点集合：

根节点的左子节点在左边界中。如果根节点不含左子节点，那么左边界就为 空 。 如果一个节点在左边界中，并且该节点有左子节点，那么它的左子节点也在左边界中。 如果一个节点在左边界中，并且该节点 不含 左子节点，那么它的右子节点就在左边界中。
最左侧的叶节点 不在 左边界中。 右边界 定义方式与 左边界 相同，只是将左替换成右。即，右边界是根节点右子树的右侧部分；叶节点 不是 右边界的组成部分；如果根节点不含右子节点，那么右边界为 空 。

叶节点 是没有任何子节点的节点。对于此问题，根节点 不是 叶节点。

给你一棵二叉树的根节点 root ，按顺序返回组成二叉树 边界 的这些值。

示例 1：

输入：root = [1,null,2,3,4]
输出：[1,3,4,2]
解释：

- 左边界为空，因为二叉树不含左子节点。
- 右边界是 [2] 。从根节点的右子节点开始的路径为 2 -> 4 ，但 4 是叶节点，所以右边界只有 2 。
- 叶节点从左到右是 [3,4] 。 按题目要求依序连接得到结果 [1] + [] + [3,4] + [2] = [1,3,4,2] 。 
1
2
3
4
5
6
7

示例 2：

输入：root = [1,2,3,4,5,6,null,null,null,7,8,9,10]
输出：[1,2,4,7,8,9,10,6,3]
解释：

- 左边界为 [2] 。从根节点的左子节点开始的路径为 2 -> 4 ，但 4 是叶节点，所以左边界只有 2 。
- 右边界是 [3,6] ，逆序为 [6,3] 。从根节点的右子节点开始的路径为 3 -> 6 -> 10 ，但 10 是叶节点。
- 叶节点从左到右是 [4,7,8,9,10]
  按题目要求依序连接得到结果 [1] + [2] + [4,7,8,9,10] + [6,3] = [1,2,4,7,8,9,10,6,3] 。
1
2
3
4
5
6
7
8

提示：

树中节点的数目在范围 [1, 104] 内
-1000 <= Node.val <= 1000
1
2

分析

分治算法

1. 左子树
2. 根节点
3. 右子树

中序遍历方式

从上图中可知，我们会发现问题描述很类似于先序遍历。实际上，遍历的顺序是一致的（除去右边界节点，它们是逆序的）。因此，我们只需要上述结果的顶点，属于左边界或者叶子节点或者右边界上。

为了区别这些节点，我们用 flagflag 符号：

• flag = 0：根节点
• flag = 1：左边界节点
• flag = 2：右边界节点
• flag = 3：其它（中间节点） 我们使用三个列表

left_boundary left_boundary，right_boundary right_boundary 和 leavesleaves 存储对应的节点。

我们按照正常的后序遍历的顺序，但当调用递归程序处理左孩子或者右孩子时，我们同时更新 flagflag 信息，表明这个节点孩子的类型。

当前节点的左孩子，我们使用函数 leftChildFlag(node, flag)。当处理左孩子时，下面可能的情况，可以通过上图来区分：

当前节点是左边界节点：左孩子也是左边界节点。例如，图中 E 和 J 的关系。 当前节点是根节点：左孩子也是左边界节点。例如，图中 A 和 B 的关系。 当前节点是右边界节点：如果右孩子不存在那么左孩子就是右边界节点。例如，上图中的 G 和
N。但是如果右孩子存在，左孩子只能作为中间节点，如图中 C 和 F。 相似地，也会有 rightChildFlag(node, flag) 来判断当前节点的右孩子：

当前节点是右边界节点：右孩子也是右边界节点。例如，图中 C 和 G 的关系。 当前节点是根节点：右孩子也是右边界节点。例如，图中 A 和 C 的关系。 当前节点是左边界节点：如果左孩子不存在那么右孩子就是右边界节点。例如，上图中的 B 和
E。但是如果右孩子存在，左孩子只能作为中间节点。 使用这些信息，我们更新 flagflag 然后用来决定那些节点会被加入到输出列表中。

coding

class TreeNode:
    def __ini
1
2
3