# 0545. Boundary of Binary Tree
###### tags: `Leetcode` `Microsoft` `Medium` `DFS` `BFS`
Link: https://leetcode.com/problems/boundary-of-binary-tree/
## 思路
### 思路一 O(N) O(N)
简单的按照题目要求一步一步来，先加root, 然后left boundary，然后leaf,然后right boundary
这里要注意不要重复加root (在递归的时候用的方法就是**加完root之后，下面的函数都是从root的child里面开始找**)
## Code
recursion

class Solution {
    List<Integer> ans;
    public List<Integer> boundaryOfBinaryTree(TreeNode root) {
        ans = new ArrayList<>();
        if(root==null) return ans;
        ans.add(root.val);
        leftBoundary(root.left);
        leafNodes(root.left);
        leafNodes(root.right);
        rightBoundary(root.right);
        return ans;
    }
    private void leftBoundary(TreeNode root){
        if(root == null) return;
        if(root.left==null && root.right==null) return;
        ans.add(root.val);
        if(root.left==null) leftBoundary(root.right);
        else leftBoundary(root.left);
    }
    private void rightBoundary(TreeNode root){
        if(root == null) return;
        if(root.left==null && root.right==null) return;
        if(root.right==null) rightBoundary(root.left);
        else rightBoundary(root.right);
        ans.add(root.val);
    }
    private void leafNodes(TreeNode root){
        if(root == null) return;
        if(root.left==null && root.right==null) ans.add(root.val);
        leafNodes(root.left);
        leafNodes(root.right);
    }
}

iterative（比较复杂）

class Solution {
    public List<Integer> boundaryOfBinaryTree(TreeNode root) {
        List<Integer> ans = new ArrayList<>();
        if(root==null) return ans;
        TreeNode curr = root;
        
        ans.add(root.val);
        
        //left boundary
        if(curr.left!=null){
            curr = curr.left;
            while(curr.left!=null||curr.right!=null){
                ans.add(curr.val);
                if(curr.left!=null) curr=curr.left;
                else curr=curr.right;
            }
        }
        
        //leaf
        curr = root;
        Stack<TreeNode> stack = new Stack<>();
        stack.add(root);
        while(!stack.isEmpty()){
            TreeNode node = stack.pop();
            if(node.left==null && node.right==null && node!=root){
                ans.add(node.val);
            }
            if(node.right!=null) stack.add(node.right);
            if(node.left!=null) stack.add(node.left);
        }
        
        //right boundary
        List<Integer> rightAns = new ArrayList<>();
        curr = root;
        if(curr.right!=null){
            curr = curr.right;
            while(curr.left!=null||curr.right!=null){
                rightAns.add(0,curr.val);
                if(curr.right!=null) curr = curr.right;
                else curr = curr.left;
            }
        }
        // Collections.reverse(rightAns);
        ans.addAll(rightAns);
        return ans;
    }
}