# 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 boundaryOfBinaryTree(TreeNode* root) { if (root == nullptr) return {}; vector 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& 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 boundaryOfBinaryTree(TreeNode root) { if (root == null) return new ArrayList<>(); List 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 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