[545. Boundary of Binary Tree] #leetcode

545_0902.java

class Solution {
	// O(n) O(n)
    public List<Integer> boundaryOfBinaryTree(TreeNode root) {
        List<Integer> res = new ArrayList<Integer>();
        
        if (root == null) return res;
        if (root.left == null && root.right == null) {
            res.add(root.val); 
            return res;
        }
        
        Boolean left = leftBoundary(root, res);
        
        List<Integer> leaf = new ArrayList<Integer>();
        leaves(root, leaf);
        if (left && leaf.get(0) == res.get(res.size()-1)) {
            res.addAll(leaf.subList(1, leaf.size()));
        } else {
            res.addAll(leaf);
        }
        
        rightBoundary(root, res);
        return res;
    }
    
    private static Boolean leftBoundary(TreeNode node, List<Integer> res) {
        if (node.left == null) {
            res.add(node.val);
            return false;
        }
        
        while (node != null) {
            res.add(node.val);
            if (node.left == null) {
                node = node.right; 
            } else {
                node = node.left;
            }
        }
        return true;
    }
    
    private static void leaves(TreeNode node, List<Integer> res) {
        if (node == null) return;
        if (node.left == null && node.right == null) {
            res.add(node.val);
            return;
        }
        leaves(node.left, res);
        leaves(node.right, res);
    }
    
    private static void rightBoundary(TreeNode node, List<Integer> res) {
        if (node.right == null) return;
        
        List<Integer> right = new ArrayList<Integer>();
        while (node != null) {
            right.add(node.val);
            if (node.right == null) {
                node = node.left; 
            } else {
                node = node.right;
            }
        }
        if (res.get(res.size()-1) == right.get(right.size()-1)) right = right.subList(0, right.size()-1);
            
        Collections.reverse(right);
        res.addAll(right.subList(0, right.size()-1));
    }
}

class Solution2 {
    public List<Integer> boundaryOfBinaryTree(TreeNode root) {
        List<Integer> res = new ArrayList<Integer>();
        if (root == null) return res;
        
        res.add(root.val);
        getBoundary(root.left, res, true, false);
        getBoundary(root.right, res, false, true);
        return res;
    }
    
    private static void getBoundary(TreeNode node, List<Integer> res, boolean lb, boolean rb) {
        if (node == null) return;
        if (lb) res.add(node.val);
        if (!lb && !rb && node.left == null && node.right == null) res.add(node.val);
        getBoundary(node.left, res, lb, rb && node.right == null);
        getBoundary(node.right, res, lb && node.left == null, rb);
        if (rb) res.add(node.val);
    }
}