返回介绍

solution / 0500-0599 / 0545.Boundary of Binary Tree / README

发布于 2024-06-17 01:03:59 字数 6541 浏览 0 评论 0 收藏 0

545. 二叉树的边界

English Version

题目描述

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

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

  • 根节点的左子节点在左边界中。如果根节点不含左子节点,那么左边界就为
  • 如果一个节点在左边界中,并且该节点有左子节点,那么它的左子节点也在左边界中。
  • 如果一个节点在左边界中,并且该节点 不含 左子节点,那么它的右子节点就在左边界中。
  • 最左侧的叶节点 不在 左边界中。

右边界 定义方式与 左边界 相同,只是将左替换成右。即,右边界是根节点右子树的右侧部分;叶节点 不是 右边界的组成部分;如果根节点不含右子节点,那么右边界为

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

给你一棵二叉树的根节点 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] 。

示例 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, 104]
  • -1000 <= Node.val <= 1000

解法

方法一

# 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: TreeNode) -> List[int]:
    self.res = []
    if not root:
      return self.res
    # root
    if not self.is_leaf(root):
      self.res.append(root.val)

    # left boundary
    t = root.left
    while t:
      if not self.is_leaf(t):
        self.res.append(t.val)
      t = t.left if t.left else t.right

    # leaves
    self.add_leaves(root)

    # right boundary(reverse order)
    s = []
    t = root.right
    while t:
      if not self.is_leaf(t):
        s.append(t.val)
      t = t.right if t.right else t.left
    while s:
      self.res.append(s.pop())

    # output
    return self.res

  def add_leaves(self, root):
    if self.is_leaf(root):
      self.res.append(root.val)
      return
    if root.left:
      self.add_leaves(root.left)
    if root.right:
      self.add_leaves(root.right)

  def is_leaf(self, node) -> bool:
    return node and node.left is None and node.right is None
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *   int val;
 *   TreeNode left;
 *   TreeNode right;
 *   TreeNode() {}
 *   TreeNode(int val) { this.val = val; }
 *   TreeNode(int val, TreeNode left, TreeNode right) {
 *     this.val = val;
 *     this.left = left;
 *     this.right = right;
 *   }
 * }
 */
class Solution {
  private List<Integer> res;

  public List<Integer> boundaryOfBinaryTree(TreeNode root) {
    if (root == null) {
      return Collections.emptyList();
    }
    res = new ArrayList<>();

    // root
    if (!isLeaf(root)) {
      res.add(root.val);
    }

    // left boundary
    TreeNode t = root.left;
    while (t != null) {
      if (!isLeaf(t)) {
        res.add(t.val);
      }
      t = t.left == null ? t.right : t.left;
    }

    // leaves
    addLeaves(root);

    // right boundary(reverse order)
    Deque<Integer> s = new ArrayDeque<>();
    t = root.right;
    while (t != null) {
      if (!isLeaf(t)) {
        s.offer(t.val);
      }
      t = t.right == null ? t.left : t.right;
    }
    while (!s.isEmpty()) {
      res.add(s.pollLast());
    }

    // output
    return res;
  }

  private void addLeaves(TreeNode root) {
    if (isLeaf(root)) {
      res.add(root.val);
      return;
    }
    if (root.left != null) {
      addLeaves(root.left);
    }
    if (root.right != null) {
      addLeaves(root.right);
    }
  }

  private boolean isLeaf(TreeNode node) {
    return node != null && node.left == null && node.right == null;
  }
}
/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *   this.val = (val===undefined ? 0 : val)
 *   this.left = (left===undefined ? null : left)
 *   this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number[]}
 */
var boundaryOfBinaryTree = function (root) {
  let leftBoundary = function (root, res) {
    while (root) {
      let curVal = root.val;
      if (root.left) {
        root = root.left;
      } else if (root.right) {
        root = root.right;
      } else {
        break;
      }
      res.push(curVal);
    }
  };
  let rightBoundary = function (root, res) {
    let stk = [];
    while (root) {
      let curVal = root.val;
      if (root.right) {
        root = root.right;
      } else if (root.left) {
        root = root.left;
      } else {
        break;
      }
      stk.push(curVal);
    }
    let len = stk.length;
    for (let i = 0; i < len; i++) {
      res.push(stk.pop());
    }
  };
  let levelBoundary = function (root, res) {
    if (root) {
      levelBoundary(root.left, res);
      if (!root.left && !root.right) {
        res.push(root.val);
      }
      levelBoundary(root.right, res);
    }
  };
  let res = [];
  if (root) {
    res.push(root.val);
    leftBoundary(root.left, res);
    if (root.left || root.right) {
      levelBoundary(root, res);
    }
    rightBoundary(root.right, res);
  }
  return res;
};

如果你对这篇内容有疑问,欢迎到本站社区发帖提问 参与讨论,获取更多帮助,或者扫码二维码加入 Web 技术交流群。

扫码二维码加入Web技术交流群

发布评论

需要 登录 才能够评论, 你可以免费 注册 一个本站的账号。
列表为空,暂无数据
    我们使用 Cookies 和其他技术来定制您的体验包括您的登录状态等。通过阅读我们的 隐私政策 了解更多相关信息。 单击 接受 或继续使用网站,即表示您同意使用 Cookies 和您的相关数据。
    原文