1. 合并二叉树

（1）BFS广度

准备两个队列

将root2 作为结果树处理（保留合并结果）

每次循环中，先得到父结点，然后处理他们的左右孩子节点，都不为空的情况下才入队

父结点在上一次循环中，就以孩子节点的身份进行了合并

class Solution {
    public TreeNode mergeTrees(TreeNode root1, TreeNode root2) {
        if(root1 == null) {
            return root2;
        }
        if(root2 == null) {
            return root1;
        }
        root2.val += root1.val;
        LinkedList<TreeNode> queue1 = new LinkedList<>();
        LinkedList<TreeNode> queue2 = new LinkedList<>();
        queue1.add(root1);
        queue2.add(root2);
        while(!queue1.isEmpty() && !queue2.isEmpty()) {
            TreeNode t1 = queue1.poll();
            TreeNode t2 = queue2.poll();
            //左子树至少一个不为空
            if(t1.left != null || t2.left != null) {
                //t1的左空了，不做处理
                if(t2.left == null) {
                    t2.left = t1.left;
                } else if(t1.left != null && t2.left != null) {
                    t2.left.val += t1.left.val;
                    queue1.add(t1.left);
                    queue2.add(t2.left);
                }
            }
            //右子树至少一个不为空
            if(t1.right != null || t2.right != null) {
                //t1的右空了，不做处理
                if(t2.right == null) {
                    t2.right = t1.right;
                } else if (t1.right != null && t2.right != null) {
                    t2.right.val += t1.right.val;
                    queue1.add(t1.right);
                    queue2.add(t2.right);
                }
            }
        }
        return root2;
    }
}

（2）DFS深度

结果树：root2（合并结果的保留）

每次递归处理传入结点的值

再调用函数，分别处理左右结点

最后返回本次处理的结点

如果传入的两个结点都为空，返回root2，因为它是结果树上的结点

class Solution {
    public TreeNode mergeTrees(TreeNode root1, TreeNode root2) {
        if(root1 == null) {
            return root2;
        }
        if(root2 == null) {
            return root1;
        }
        root2.val += root1.val;
        root2.left = mergeTrees(root1.left, root2.left);
        root2.right = mergeTrees(root1.right, root2.right);
        return root2;
    }
}

2.填充每个节点的下一个右侧节点指针

（1）层次遍历法 BFS

用队列保存每一层不为空的结点

然后每次操作一层的结点：循环开始时得到队列大小既为这层的节点数量

每一层最后一个结点的next 为 null

class Solution {
    public Node connect(Node root) {
        if(root != null) {
            LinkedList<Node> queue = new LinkedList<Node>();
            queue.add(root);
            while(!queue.isEmpty()) {
                int size = queue.size();
                Node temp = null;
                for(int i = 0; i < size - 1; i++) {
                    temp = queue.poll();
                    temp.next = queue.getFirst();
                    helper(queue, temp);
                }
                temp = queue.poll();
                temp.next = null;
                helper(queue, temp);
            }
        }
        return root;
    }

    private void helper(LinkedList<Node> queue, Node temp) {
        if(temp.left != null) {
            queue.add(temp.left);
        }
        if(temp.right != null) {
            queue.add(temp.right);
        }
    }

}

（2）进阶——DFS

所有结点next 默认为null

函数传入结点不为空，若左节点空，则为叶结点，不做处理

则递归只需处理本次传入结点的左右孩子节点的next

左孩子节点的next ： 为 右孩子节点

右孩子节点的next ：只有当父结点的next不为空，则为父结点next指向结点的左节点（很容易从图中看出）

再将左右孩子节点作为父结点调用函数处理

class Solution {
    public Node connect(Node root) {
        if(root == null) {
            return root;
        }
        if(root.left == null) {
            return root;
        }
        root.left.next = root.right;
        if(root.next != null) {
            root.right.next = root.next.left;
        }
        connect(root.left);
        connect(root.right);
        return root;
    }
}