Leetcode刷题——623. 在二叉树中增加一行

是今天的每日一题，题目地址：623. 在二叉树中增加一行

思路

看到对每一层进行操作，首先就是想到层次遍历。当现在的深度等于给定的depth-1时记录当前节点（可以直接用queue，当时没想到）开始操作，操作时要注意区分注意要区分孩子是否为空的情况：
孩子为空，直接添加；孩子不为空，相当于加一层，添到后面去。
代码：

 public TreeNode addOneRow(TreeNode root, int val, int depth) {
    
      if (depth == 1) {
    
            TreeNode node = new TreeNode(val);
            node.left = root;
            return node;
        }
        Queue<TreeNode> queue = new LinkedList<>();
        if(root==null){
    
            return new TreeNode(val);
        }
        queue.offer(root);
        int nowDepth = 0;
        while (!queue.isEmpty()) {
    
            nowDepth++;
            int len = queue.size() - 1;
            List<TreeNode> list = new ArrayList<>();
            while (len-- >= 0) {
    
                TreeNode poll = queue.poll();
                if(nowDepth == depth - 1){
    
                    list.add(poll);
                }
                if (poll.left != null) {
    
                    queue.offer(poll.left);
                }
                if (poll.right != null) {
    
                    queue.offer(poll.right);
                }
            }
// 目标
            if(nowDepth==depth-1){
    
                //最后一行
                    for (TreeNode node : list) {
    
                      if(node.left!=null){
    
                          TreeNode newNode = new TreeNode(val);
                          newNode.left=node.left;
                          node.left=newNode;
                      }
                      else {
    
                          node.left=new TreeNode(val);
                      }
                        if(node.right!=null){
    
                            TreeNode newNode = new TreeNode(val);
                            newNode.right=node.right;
                            node.right=newNode;
                        }
                        else {
    
                            node.right=new TreeNode(val);
                        }
                    
                }
                break;
            }
        }
        return root;
    }

改进

之所以代码这么冗余是因为我忽略了TreeNode有另一种构造方法，可以直接声明左子树和右子树，就避免了很多冗余的操作。

public TreeNode addOneRow(TreeNode root, int val, int depth) {
    
       if (depth == 1) {
    
            TreeNode node = new TreeNode(val);
            node.left = root;
            return node;
        }
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        int newDepth = 0;
        while (!queue.isEmpty()){
    
            newDepth++;
            int len = queue.size()-1;
            if(newDepth == depth-1){
    
                while (!queue.isEmpty()){
    
                    TreeNode poll = queue.poll();
                    poll.left =new TreeNode(val,poll.left,null);
                    poll.right =new TreeNode(val,null,poll.right);
                }
                break;
            }else {
    
                while (len-- >= 0) {
    
                    TreeNode peek = queue.poll();
                    if (peek.left != null) queue.offer(peek.left);
                    if (peek.right != null) queue.offer(peek.right);
                }
            }
        }
        return root;
    }