二叉树的边界

/*
 * 题目思路：
 * 1. 使用流处理来实现二叉树的边界遍历。
 * 2. 找到左边界、叶子节点、右边界，并合并成结果。
 */
 
import java.util.*;
import java.util.stream.Collectors;
import java.util.stream.Stream;
 
class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int x) { val = x; }
}
 
public class BoundaryOfBinaryTreeStream {
    public List<Integer> boundaryOfBinaryTree(TreeNode root) {
        if (root == null) return Collections.emptyList();
        List<Integer> leftBoundary = new ArrayList<>();
        List<Integer> rightBoundary = new ArrayList<>();
        List<Integer> leaves = new ArrayList<>();
        if (!isLeaf(root)) leftBoundary.add(root.val);
        collectLeftBoundary(root.left, leftBoundary);
        collectLeaves(root, leaves);
        collectRightBoundary(root.right, rightBoundary);
        Collections.reverse(rightBoundary);
        return Stream.of(leftBoundary, leaves, rightBoundary)
                     .flatMap(Collection::stream)
                     .collect(Collectors.toList());
    }
 
    private void collectLeftBoundary(TreeNode node, List<Integer> res) {
        while (node != null) {
            if (!isLeaf(node)) res.add(node.val);
            if (node.left != null) node = node.left;
            else node = node.right;
        }
    }
 
    private void collectLeaves(TreeNode node, List<Integer> res) {
        if (isLeaf(node)) {
            res.add(node.val);
            return;
        }
        if (node.left != null) collectLeaves(node.left, res);
        if (node.right != null) collectLeaves(node.right, res);
    }
 
    private void collectRightBoundary(TreeNode node, List<Integer> res) {
        while (node != null) {
            if (!isLeaf(node)) res.add(node.val);
            if (node.right != null) node = node.right;
            else node = node.left;
        }
    }
 
    private boolean isLeaf(TreeNode node) {
        return node.left == null && node.right == null;
    }
}