[leetCode 623]二叉树增加一行（每日一题）

采用层序遍历的方法，当遍历到深度为depth-1的时候，对这一层的节点进行处理，然后返回即可。

层序遍历采用队列的形式，每次读一层的节点。

public class Solution {
    public TreeNode addOneRow(TreeNode root, int val, int depth) {
        //根节点插入的话就直接处理
        if (depth == 1) {
            TreeNode node = new TreeNode(val);
            node.left = root;
            return node;
        }
        int cur = 1;
        //队列，用来存放节点
        Queue queue = new ArrayDeque<>();
        queue.add(root);
        while (queue != null) {
            //记录当前的size，因为队列size在操作的时候是会改变的
            int size = queue.size();
            //每次for循环就是对这层的所有节点操作
            for (int i = 0; i < size; i++) {
                if (cur + 1 == depth) {
                    add(queue.poll(), val);
                } else {
                    TreeNode node = queue.poll();
                    if (node.left != null) queue.add(node.left);
                    if (node.right != null) queue.add(node.right);
                }
            }
            if (cur + 1 == depth) break;
            cur++;
        }
        return root;
    }

    private void add(TreeNode node, int val) {
        TreeNode left = node.left;
        TreeNode right = node.right;
        TreeNode node1 = new TreeNode(val);
        TreeNode node2 = new TreeNode(val);
        node.left = node1;
        node.right = node2;
        node1.left = left;
        node2.right = right;
    }
}