545. Boundary of Binary Tree

解法一

思路

我觉得这是很经典的一道题，运用到了 DFS 和 stack 以及 list 的操作。
We can spearate the problem into three subproblems. Find left boundary, find leaves and find right boundary.
For left boundary, we always check the left child first and then right child if left child is null. If the child is not a leaf, add it into the result list.
For adding leaves, we use dfs to search all leaves from left to right and add them into list. The exit is when we find a leaf -> the node has no child.
For adding right boundary, it is similar to adding left boundary. The only difference is that we check its right child first and then left.

代码

class Solution{
    public List<Integer> boundaryOfBinaryTree(TreeNode root) {
        List<Integer> boundary = new ArrayList<>();
        if (root == null) {
          return boundary;
        }
        // No matter left subtree or/and right subtree is null, root is always the first one
        boundary.add(root.val);
        TreeNode t = root.left;
        while (t != null) {
            if (!isLeaf(t)) {
                boundary.add(t.val);
            }
            if (t.left != null) {
                t =t.left;
            } else if (t.right != null) {
                t = t.right;
            }
        }
        // Avoid adding root twice is toor itself is a leaf
        if (!isLeaf(root)) {
            addLeaves(boundary, root);
        }

        t = root.right;
        Stack<Integer> stack = new Stack<>();
        while (t != null) {
            if (!isLeaf(t)) {
                stack.push(t.val);
            }
            if (t.right != null) {
                t = t.right;
            } else if (t.left != null) {
                t = t.left;
            }
        }
        while (!stack.isEmpty()) {
            boundary.add(stack.pop());
        }
        return boundary;
    }

    private boolean isLeaf(TreeNode node) {
        return node.right == null && node.left == null;
    }

    private void addLeaves(List<Integer> boundary, TreeNode node) {
        if (isLeaf(node)) {
            boundary.add(node.val);
        } else {
            if (node.left != null) {
                addLeaves(boundary, node.left);
            }
            if (node.right != null) {
                addLeaves(boundary, node.right);
            }
        }
    }
}