• Time:O(n)
• Space:O(h)

## C++

``````class Solution {
public:
vector<int> boundaryOfBinaryTree(TreeNode* root) {
if (!root)
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)
return;
if (lb)
ans.push_back(root->val);
if (!lb && !rb && !root->left && !root->right)
ans.push_back(root->val);

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

## JAVA

``````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)
if (!lb && !rb && root.left == null && root.right == null)

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

## Python

``````class Solution:
def boundaryOfBinaryTree(self, root: Optional[TreeNode]) -> List[int]:
if root is None:
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
``````