/**
(error!)
1. 分别对应3种情况
1.1 从根一直访问左节点的顺序集合(删除)
1.2 从左到右按层遍历的顺序集合(删除)
1.3 从根一直访问右节点的逆序集合(删除)
(error!)

1. 分别对应3种情况
1.1 从根开始一直向下遍历, 优先按左儿子变量的顺序集合
1.2 按从左到右 dfs的 所有左右子树都为空的顺序集合
1.3 从根开始一直向下遍历, 优先按右儿子变量的逆序集合

1.4 题意好像有点歧义: 需要特判下root 有无左右子树

2. 按序合并上述集合, 合并时去重, 
3. 看来读题很重要......

*/


/**
1. 另一种更简单的方法, 搜索是标记当前节点是否是所需节点
1.2 向左搜索时, 右边界必定没有右子树
1.3 向右搜索时, 左边界必定没有左子树

2. 追加结果集时:
2.1 优先追加左边界
2.2 不是左边界的且没有左右子树的为叶子节点
2.3 是右边界 且不是叶子节点的为右边界,  有边界要等 左边界和下边界 收集完再收集

即:
3.1 搜索顺序: 添加左边界, 添加叶子, 搜索左子树, 搜索右子树, 添加有边界
3.2 搜索状态:  local: root, isLeftBound, isRightBound  |  global: result
3.3 剪枝: root == null 跳出

*/


/**
 * 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) {
        // return merge(root);

        List<Integer> res = new ArrayList<>();
        search(root, true, true, res);
        return res;
    }

    public void search(TreeNode root, boolean isLeftBound, boolean isRightBound, List<Integer> res){
        if (root == null) return;

        if (isLeftBound){
            res.add(root.val);
        } else if (root.left == null && root.right == null){
            res.add(root.val);
        } 
        // 向左搜索只有没有右节点时才能是右边界
        search(root.left, isLeftBound, !isLeftBound && isRightBound && root.right == null, res);
        search(root.right, isLeftBound && !isRightBound && root.left == null, isRightBound, res);
        if (isRightBound && !isLeftBound && (root.left != null || root.right != null)){
            res.add(root.val);
        }
    }

    public List<Integer> merge(TreeNode root){
        List<TreeNode> bound = getLeft(root);
        Set<TreeNode> set = new HashSet<>(bound);
        List<TreeNode> leaf = getLeaf(root);
        List<TreeNode> right = getRight(root);

        for (int i = 0; i < leaf.size(); i++){
            TreeNode node = leaf.get(i);
            if (!set.contains(node)){
                bound.add(node);
                set.add(node);
            }
        }

        for (int i = right.size() -1 ; i >= 0;  i--){
            TreeNode node = right.get(i);
            if (!set.contains(node)){
                bound.add(node);
                set.add(node);
            }
        }
        if (root == null) return new ArrayList<Integer>();
        return bound.stream().map(x->x.val).collect(Collectors.toList());
    }

    public List<TreeNode> getLeft(TreeNode root){
        List<TreeNode> list = new ArrayList<>();
        if (root == null) return list;
        if (root.left == null){
            list.add(root);
            return list;
        }
        while (root != null){
            list.add(root);
            if (root.left != null)  root = root.left;
            else root = root.right;
        }
        return list;
    }

    public List<TreeNode> getRight(TreeNode root){
        List<TreeNode> list = new ArrayList<>();
        if (root == null) return list;
        if (root.right == null){
            list.add(root);
            return list;
        }

        while (root != null){
            list.add(root);
            if (root.right != null)  root = root.right;
            else root = root.left;
        }
        return list;
    }

    public List<TreeNode> getLeaf(TreeNode root){
        List<TreeNode> list = new ArrayList<>();
        dfs(root, list);
        return list;
    }

    private void dfs(TreeNode root, List<TreeNode> list){
        if (root == null) return;

        if (root.left == null && root.right == null){
            list.add(root);
            return;
        }

        if (root.left != null) dfs(root.left, list);
        if (root.right != null) dfs(root.right, list);
    }

    public List<TreeNode> getLast(TreeNode root){

        List<TreeNode> list = new ArrayList<>();
        if (root == null) return list;
        Queue<TreeNode>[] qs = new Queue[2];
        qs[0] = new LinkedList<TreeNode>();
        qs[1] = new LinkedList<TreeNode>();
        int cur = 0;
        qs[cur].offer(root);
        while (!qs[cur].isEmpty()){

            list.clear();
            while (!qs[cur].isEmpty()) {
                TreeNode node = qs[cur].poll();
                if (node.left != null)  qs[cur^1].offer(node.left);
                if (node.right != null)  qs[cur^1].offer(node.right);
                list.add(node);
            }
            cur = cur ^ 1;
            // 要注意是异或
        }

        return list;
    }

}