Skip to content

545. Boundary of Binary Tree 👎

  • Time: $O(n)$
  • Space: $O(h)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
class Solution {
 public:
  vector<int> boundaryOfBinaryTree(TreeNode* root) {
    if (root == nullptr)
      return {};
    vector<int> ans{root->val};
    dfs(root->left, true, false, ans);
    dfs(root->right, false, true, ans);
    return ans;
  }

 private:
  /**
   * 1. root->left is left boundary if root is left boundary
   *    root->right if left boundary if root->left == nullptr
   * 2. same applys for right boundary
   * 3. if root is left boundary, add it before 2 children - preorder
   *    if root is right boundary, add it after 2 children - postorder
   * 4. a leaf that is neighter left/right boundary belongs to the bottom
   */
  void dfs(TreeNode* root, bool lb, bool rb, vector<int>& ans) {
    if (root == nullptr)
      return;
    if (lb)
      ans.push_back(root->val);
    if (!lb && !rb && root->left == nullptr && root->right != nullptr)
      ans.push_back(root->val);

    dfs(root->left, lb, rb && root->right == nullptr, ans);
    dfs(root->right, lb && root->left == nullptr, rb, ans);
    if (rb)
      ans.push_back(root->val);
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
class Solution {
  public List<Integer> boundaryOfBinaryTree(TreeNode root) {
    if (root == null)
      return new ArrayList<>();
    List<Integer> ans = new ArrayList<>(Arrays.asList(root.val));
    dfs(root.left, true, false, ans);
    dfs(root.right, false, true, ans);
    return ans;
  }

  /**
   * 1. root.left is left boundary if root is left boundary
   *    root.right if left boundary if root.left == null
   * 2. same applys for right boundary
   * 3. if root is left boundary, add it before 2 children - preorder
   *    if root is right boundary, add it after 2 children - postorder
   * 4. a leaf that is neighter left/right boundary belongs to the bottom
   */
  private void dfs(TreeNode root, boolean lb, boolean rb, List<Integer> ans) {
    if (root == null)
      return;
    if (lb)
      ans.add(root.val);
    if (!lb && !rb && root.left == null && root.right == null)
      ans.add(root.val);

    dfs(root.left, lb, rb && root.right == null, ans);
    dfs(root.right, lb && root.left == null, rb, ans);
    if (rb)
      ans.add(root.val);
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
class Solution:
  def boundaryOfBinaryTree(self, root: Optional[TreeNode]) -> List[int]:
    if not root:
      return []

    ans = [root.val]

    def dfs(root: Optional[TreeNode], lb: bool, rb: bool):
      """
      1. root.left is left boundary if root is left boundary
         root.right if left boundary if root.left is None
      2. same applys for right boundary
      3. if root is left boundary, add it before 2 children - preorder
         if root is right boundary, add it after 2 children - postorder
      4. a leaf that is neighter left/right boundary belongs to the bottom
      """
      if not root:
        return
      if lb:
        ans.append(root.val)
      if not lb and not rb and not root.left and not root.right:
        ans.append(root.val)

      dfs(root.left, lb, rb and not root.right)
      dfs(root.right, lb and not root.left, rb)
      if rb:
        ans.append(root.val)

    dfs(root.left, True, False)
    dfs(root.right, False, True)
    return ans