leetcode623. 在二叉树中增加一行

leetcode623. 在二叉树中增加一行

三月 14, 2020

leetcode623. 在二叉树中增加一行

给定一个二叉树，根节点为第1层，深度为 1。在其第 d 层追加一行值为 v 的节点。

添加规则：给定一个深度值 d （正整数），针对深度为 d-1 层的每一非空节点 N，为 N 创建两个值为 v 的左子树和右子树。

将 N 原先的左子树，连接为新节点 v 的左子树；将 N 原先的右子树，连接为新节点 v 的右子树。

如果 d 的值为 1，深度 d - 1 不存在，则创建一个新的根节点 v，原先的整棵树将作为 v 的左子树。

示例 1:
输入:
二叉树如下所示:

     4
   /   \
  2     6
 / \   / 
3   1 5

v = 1
d = 2

输出: 

     4
    / \
   1   1
  /     \
 2       6
/ \     / 
3  1   5

层序遍历

果然不用递归就会好想很多.遍历到当前层就开始操作,没什么可说的了,

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
public TreeNode addOneRow(TreeNode root, int v, int d) {
        if(d==1){
            TreeNode newNode=new TreeNode(v);
            newNode.left=root;
            return newNode;
        }
        Queue<TreeNode>queue=new LinkedList<>();
        queue.add(root);
        int count=1;
        while(!queue.isEmpty()&&(d-1)>=count){
            int level=queue.size();
            for(int i=0;i<level;i++){
                TreeNode node=queue.poll();
                if(d-1==count){
                    TreeNode left=node.left;
                    TreeNode right=node.right;
                    node.left=new TreeNode(v);
                    node.right=new TreeNode(v);
                    node.left.left=left;
                    node.right.right=right;
                }else{
                    if(node.left!=null)queue.add(node.left);
                    if(node.right!=null)queue.add(node.right);
                }
            }
            count++;
        }
        return root;
    }

leetcode 48/100