Level Order Traverse

1. BFS - 关键在于每一层的数量 queue.size()
2. DFS -

Populating next right pointers in each node

因为题目的条件很完美，用最简单直接的思路去考虑，分几种情况讨论

1. root，不需要处理
2. left node, root.left.next = root.right
3. right node, root.right.next = root.next.left 只需要在赋值之前，进行null check

//recursive O(n), space O(logN)
public void connect(TreeLinkNode root) {
        if (root == null) return;

         if (root.left == null || root.right == null) return;

         root.left.next = root.right;
         if (root.next != null)
             root.right.next = root.next.left;

         connect(root.left);
         connect(root.right);
 }

 //iterative 为了保证spaceO(1)
 public void connect(TreeLinkNode root) {
        if (root == null) return;

        while (root != null) {
            TreeLinkNode cur = root;
            while (cur != null) { //这一层节点的遍历
                if (cur.left != null) {
                    cur.left.next = cur.right;
                    if (cur.next != null) {
                        cur.right.next = cur.next.left;
                    }
                }

                cur = cur.next;
            }
            root = root.left;
        }        
    }

Populating next right pointers in each node II

还是按照前一题的思路的话，就会发现不断在校正各种test case，细节越来越多，通常这样的话，就需要跳出来，换思路

1. 简单暴力的思路，用level order traverse遍历，获取每一层的节点，存放在list里，然后再遍历list中每个点，设定next指针

2. 利用上一题的迭代思路，因为在迭代过程中，我们可以知道，上一层的next是已经设定好的了，只需要解决

   1. 在中间有空节点的话，如何通过上一层的next，来找到这一层的正确的节点，这个过程对于每个节点都会用到，可以抽象出来称为一个方法
   2. 如果这一层最左边有空缺的话，如何在进入下一层的时候找到正确的起点
      • 引入dummy node来找到正确的起点，适用于这种无法确定起点的情况（这样就可以用node.next而不用担心null）

Binary Tree Right Side View

• 最简单直接的思路，套用level order的模板，把每一行最后一个点加入到result里
• 发现规律是在每一层，只出一个点。即为当前层数（root为第0层开始算）和result size大小相等时候，加入这个点。并且先右后左。

public void helper(TreeNode root, int level, List<Integer> results) {
        if (root == null) return;

        if (level == results.size())
            results.add(root.val);

        helper(root.right, level+1, results);
        helper(root.left, level+1, results);
    }

    public List<Integer> rightSideView(TreeNode root) {
        List<Integer> results = new ArrayList<>();
        if (root == null) return results;
        helper(root, 0, results);
        return results;
    }

Binary Tree Serialization

最直接的思路是层序遍历

// Encodes a tree to a single string.
    public String serialize(TreeNode root) {
        if (root == null) return "";
        Queue<TreeNode> q = new LinkedList<>();
        StringBuilder res = new StringBuilder();
        q.add(root);
        while (!q.isEmpty()) {
            TreeNode node = q.poll();
            if (node == null) {
                res.append("null,");
                continue;
            }
            res.append(node.val + ",");
            q.add(node.left);
            q.add(node.right);
        }
        return res.toString();
    }

    // Decodes your encoded data to tree.
    public TreeNode deserialize(String data) {
        if (data == "") return null;
        Queue<TreeNode> q = new LinkedList<>();
        String[] values = data.split(",");
        TreeNode root = new TreeNode(Integer.parseInt(values[0]));
        q.add(root);
        for (int i = 1; i < values.length; i++) {
            TreeNode parent = q.poll();
            if (!values[i].equals("null")) {
                TreeNode left = new TreeNode(Integer.parseInt(values[i]));
                parent.left = left;
                q.add(left);
            }
            if (!values[++i].equals("null")) {
                TreeNode right = new TreeNode(Integer.parseInt(values[i]));
                parent.right = right;
                q.add(right);
            }
        }
        return root;
    }