LeetCode 545. 二叉树的边界（前序+后序）

1. 题目

给定一棵二叉树，以逆时针顺序从根开始返回其边界。边界按顺序包括左边界、叶子结点和右边界而不包括重复的结点。 (结点的值可能重复)

左边界的定义是从根到最左侧结点的路径。右边界的定义是从根到最右侧结点的路径。若根没有左子树或右子树，则根自身就是左边界或右边界。注意该定义只对输入的二叉树有效，而对子树无效。

最左侧结点的定义是：在左子树存在时总是优先访问，如果不存在左子树则访问右子树。重复以上操作，首先抵达的结点就是最左侧结点。

最右侧结点的定义方式相同，只是将左替换成右。

示例 1
输入:
  1
   
    2
   / 
  3   4
输出:
[1, 3, 4, 2]
解析:
根不存在左子树，故根自身即为左边界。
叶子结点是3和4。
右边界是1，2，4。注意逆时针顺序输出需要你输出时调整右边界顺序。
以逆时针顺序无重复地排列边界，得到答案[1,3,4,2]。

示例 2
输入:
    ____1_____
   /          
  2            3
 /           / 
4   5        6   
   /       / 
  7   8    9  10  
       
输出:
[1,2,4,7,8,9,10,6,3]

解析:
左边界是结点1,2,4。(根据定义，4是最左侧结点)
叶子结点是结点4,7,8,9,10。
右边界是结点1,3,6,10。(10是最右侧结点)
以逆时针顺序无重复地排列边界，得到答案 [1,2,4,7,8,9,10,6,3]。

题意: 高频题，必须熟练掌握。逆时针打印二叉树边界。

解题思路：
根据观察，我们发现

当node为leftBound左边界时，node.left也是左边界
当node为leftBound左边界时，node.left为空，则node.right也可以leftBound左边界。
Bottom的所有都要加入其中。
rightBound也是如此。
我们可以循环调用dfs，初始化leftBound和rightBound两个boolean参数，一层层判断。先加入左边，加入bottom，然后得到两个子树加入，最后加入右边界。

代码如下：

/**
    * node.left is left bound if node is left bound;
    * node.right could also be left bound if node is left bound && node has no left child;
    * Same applys for right bound;
    * if node is left bound, add it before 2 child - pre order;
    * if node is right bound, add it after 2 child - post order;
    * A leaf node that is neither left or right bound belongs to the bottom line;
    */
    public List<Integer> boundaryOfBinaryTree(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        if (root == null) return res;
        res.add(root.val);
        getBounds(root.left, res, true, false);
        getBounds(root.right, res, false, true);
        return res;
    }
    public void getBounds(TreeNode node, List<Integer> res, boolean leftBound, boolean rightBound) {
        if (node == null) return;
        if (leftBound) {
            res.add(node.val);
        }
        //add bottom
        if(!leftBound && !rightBound && node.left == null && node.right == null) {
            res.add(node.val);
        }
        getBounds(node.left, res, leftBound, rightBound && node.right == null);
        getBounds(node.right, res, leftBound && node.left == null, rightBound);
        if (rightBound) {
            res.add(node.val);
        }
        
        
    }