545. Boundary of Binary Tree

一开始没有好好看题目描述，完全不知道怎么做
后来发现题目已经说的很清楚了，基本就是一个recursion
题目如下
"Given a binary tree, return the values of its boundary in anti-clockwise direction starting from root. Boundary includes left boundary, leaves, and right boundary in order without duplicate nodes.

Left boundary is defined as the path from root to the left-most node. Right boundary is defined as the path from root to the right-most node. If the root doesn't have left subtree or right subtree, then the root itself is left boundary or right boundary. Note this definition only applies to the input binary tree, and not applies to any subtrees.

The left-most node is defined as a leaf node you could reach when you always firstly travel to the left subtree if exists. If not, travel to the right subtree. Repeat until you reach a leaf node.

The right-most node is also defined by the same way with left and right exchanged."


edge cases很多
我觉得避免出错的方法就是把这个boundary看成4edges，root is the upper boundary
Searching left / right only takes care of the paths without root
Searching leaves only takes care of leaves when the root is not a leaf itself

看了一个答案发现我处理seachRight的时候，add(index, root.val) 这个思路好蠢！
因为是递归啊递归！可以直接先访问child然后再add， 就是reverse order了！
写法如下

Polished Version
76.12 %
class Solution {
    public List<Integer> boundaryOfBinaryTree(TreeNode root) {
        List<Integer> result = new ArrayList<>();
        if (root == null) return result;
       
        result.add(root.val);
        if (root.left != null) {
            searchLeft(root.left, result);
        }
        if (root.left != null || root.right != null) {
            searchLeaves(root, result);
        }
        if (root.right != null) {
            searchRight(root.right, result);
        }
        return result;
    }
   
    private void searchLeft(TreeNode root, List<Integer> path) {
        if (root.left == null && root.right == null) {
            // path.add(root.val); // -> searchLeaves takes() care of this node
            return;
        }
        path.add(root.val);
        if (root.left != null) { // travel to left
            searchLeft(root.left, path);
        } else { // travel to right
            searchLeft(root.right, path);
        }
    }
    private void searchLeaves(TreeNode root, List<Integer> leaves) {
        if (root.left == null && root.right == null) {
            leaves.add(root.val);
            return;
        }
        if (root.left != null) {
            searchLeaves(root.left, leaves);
        }
        if (root.right != null) {
            searchLeaves(root.right, leaves);
        }
    }
   
    private void searchRight(TreeNode root, List<Integer> path) {
        if (root.left == null && root.right == null) {
            return;
        }
        if (root.right != null) {
            searchRight(root.right, path);
        } else {
            searchRight(root.left, path);
        }
        path.add(root.val);
    }
}



Naive Version
53.64 %
class Solution {
    public List<Integer> boundaryOfBinaryTree(TreeNode root) {
        List<Integer> result = new ArrayList<>();
        if (root == null) return result;
     
        result.add(root.val);
        if (root.left != null) {
            searchLeft(root.left, result);
        }
        if (root.left != null || root.right != null) {
            searchLeaves(root, result);
        }
        if (root.right != null) {
            searchRight(root.right, result, result.size());
        }
        return result;
    }
 
    private void searchLeft(TreeNode root, List<Integer> path) {
        if (root.left == null && root.right == null) {
            // path.add(root.val); // -> searchLeaves takes() care of this node
            return;
        }
        path.add(root.val);
        if (root.left != null) { // travel to left
            searchLeft(root.left, path);
        } else { // travel to right
            searchLeft(root.right, path);
        }
    }
    private void searchLeaves(TreeNode root, List<Integer> leaves) {
        if (root.left == null && root.right == null) {
            leaves.add(root.val);
            return;
        }
        if (root.left != null) {
            searchLeaves(root.left, leaves);
        }
        if (root.right != null) {
            searchLeaves(root.right, leaves);
        }
    }
 
    private void searchRight(TreeNode root, List<Integer> path, int index) {
        if (root.left == null && root.right == null) {
            return;
        }
        if (path.size() == index) {
            path.add(root.val);
        } else {
            path.add(index, root.val);
        }
        if (root.right != null) {
            searchRight(root.right, path, index);
        } else {
            searchRight(root.left, path, index);
        }
    }
}