545.Boundary of Binary Tree

1-

https://leetcode.com/problems/boundary-of-binary-tree/solution/

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public boolean isLeaf(TreeNode root){
        return root.left == null && root.right == null;
    }

    public void addLeaf(List<Integer> ans, TreeNode root){
        if(isLeaf(root)){
            ans.add(root.val);
        }
        else{
            if(root.left != null)
                addLeaf(ans, root.left);
            if(root.right != null)
                addLeaf(ans, root.right);
        }
    }

    public List<Integer> boundaryOfBinaryTree(TreeNode root) {
        List<Integer> ans = new ArrayList<>();
        if(root == null)
            return ans;

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

        //Add left
        TreeNode current = root.left;
        while(current != null){
            if(!isLeaf(current)){
                ans.add(current.val);
            }
            if(current.left != null){
                current = current.left;
            }
            else{
                current = current.right;
            }
        }
        //Add leaf recursively
        addLeaf(ans, root);

        //Add right
        current = root.right;
        Deque<TreeNode> stack = new ArrayDeque<>();
        while(current != null){
            if(!isLeaf(current)){
                stack.push(current);
            }
            if(current.right != null){
                current = current.right;
            }
            else{
                current = current.left;
            }
        }
        while(!stack.isEmpty()){
            ans.add(stack.pop().val);
        }
        return ans;
    }
}

2- Totally Recursive, More Clearly

https://discuss.leetcode.com/topic/84275/java-12ms-left-boundary-left-leaves-right-leaves-right-boundary/10

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public List<Integer> boundaryOfBinaryTree(TreeNode root) {
        List<Integer> ans = new ArrayList<>();
        if(root == null){
            return ans;
        }
        ans.add(root.val);
        addLeftBoundry(ans, root.left);
        addLeaf(ans, root.left);
        addLeaf(ans, root.right);
        addRightBoundry(ans, root.right);
        return ans;
    }
    public boolean isLeaf(TreeNode root){
        return root.left == null && root.right == null;
    }

    public void addLeftBoundry(List<Integer> ans, TreeNode root){
        if(root == null ||isLeaf(root))
            return;
        ans.add(root.val);
        if(root.left == null){
            addLeftBoundry(ans, root.right);
        }
        else{
            addLeftBoundry(ans, root.left);
        }
    }

    public void addRightBoundry(List<Integer> ans, TreeNode root){
        if(root == null ||isLeaf(root))
            return;
        if(root.right == null){
            addRightBoundry(ans, root.left);
        }
        else{
            addRightBoundry(ans, root.right);
        }
        ans.add(root.val);
    }
    public void addLeaf(List<Integer> ans, TreeNode root){
        if(root == null)
            return;
        if(isLeaf(root)){
            ans.add(root.val);
            return;
        }
        addLeaf(ans, root.left);
        addLeaf(ans, root.right);
    }
}