Boundary of Binary Tree (FB, G, Amazon)

先通过level traversal, 拿到每层node和leaf nodes, hashset保存已访问过的node

• 将每层第一个node添加进left bound list, 最后一个node添加进right bound list.

• ans加入left bound, leaf nodes, right bound. hashset判断, 已经添加过的就不要再添加了.

• 很多地方可以与面试官讨论.

环形遍历, 其实就是输出left boundary, leaves, 和right boundary, 然而写了一个却不过, 原因是

1
 \
  2
 / \
3   4

我输出的是 [1, 2, 3, 4], 正确的是[1, 3, 4, 2], 还是要考虑vertical order, 这么想这个问题就太复杂了.

好吧, 事实证明OJ把boundary严格定义了, 按OJ的定义, 输出为 [1,2,6,7,9,8,4,3].

然而我的算法会给出[1,2,4,5,6,7,9,8,4,3]

    1
   / \
  2   3
     /
    4
   / \
  5   8
 / \   \
6   7   9

public class Solution {
    public List<Integer> boundaryOfBinaryTree(TreeNode root) {
        List<List<TreeNode>> level = new ArrayList<List<TreeNode>>();
        List<TreeNode> leafList = new ArrayList<TreeNode>();
        traverseLevel(root, level, leafList);
        List<TreeNode> leftBound = new ArrayList<TreeNode>();
        List<TreeNode> rightBound = new ArrayList<TreeNode>();
        HashSet<TreeNode> set = new HashSet<TreeNode>();
        for(int i=0;i<level.size();i++){
            List<TreeNode> row = level.get(i);
            leftBound.add(row.get(0)); set.add(row.get(0));
            if(row.size()>=2){
                rightBound.add(row.get(row.size()-1)); set.add(row.get(row.size()-1));
            }
        }

        List<Integer> ans = new ArrayList<Integer>();
        for(TreeNode node : leftBound) ans.add(node.val);
        for(TreeNode node : leafList)
            if(!set.contains(node)) ans.add(node.val);
        for(int i=rightBound.size()-1;i>=0;i--)
            ans.add(rightBound.get(i).val);
        return ans;
    }

    public void traverseLevel(TreeNode root, List<List<TreeNode>> level, List<TreeNode> leafList){
        Queue<TreeNode> queue = new LinkedList<TreeNode>();
        queue.add(root);
        while(!queue.isEmpty()){
            level.add(new ArrayList<TreeNode>(queue));
            int size = queue.size();
            for(int i=0;i<size;i++){
                TreeNode tmp = queue.poll();
                if(tmp.left!=null) queue.add(tmp.left);
                if(tmp.right!=null) queue.add(tmp.right);
                if(tmp.left==null && tmp.right==null) leafList.add(tmp);
            }
        }
    }
}

网上论坛上的解法: https://leetcode.com/problems/boundary-of-binary-tree/#/solutions

用递归的想法严格按照顺序, 先搜left bound, 再 left leaf, 再 right leaf, 再 right bound. 搜索left bound的时候,

List<Integer> nodes = new ArrayList<>(1000);
public List<Integer> boundaryOfBinaryTree(TreeNode root) {

    if(root == null) return nodes;

    nodes.add(root.val);
    leftBoundary(root.left);
    leaves(root.left);
    leaves(root.right);
    rightBoundary(root.right);

    return nodes;
}
public void leftBoundary(TreeNode root) {
    if(root == null || (root.left == null && root.right == null)) return;
    nodes.add(root.val);
    if(root.left == null) leftBoundary(root.right);
    else leftBoundary(root.left);
}
public void rightBoundary(TreeNode root) {
    if(root == null || (root.right == null && root.left == null)) return;
    if(root.right == null)rightBoundary(root.left);
    else rightBoundary(root.right);
    nodes.add(root.val); // add after child visit(reverse)
}
public void leaves(TreeNode root) {
    if(root == null) return;
    if(root.left == null && root.right == null) {
        nodes.add(root.val);
        return;
    }
    leaves(root.left);
    leaves(root.right);
}