首页 > itarticle > leetcode_【623】在二叉树中增加一行

leetcode_【623】在二叉树中增加一行

admin 11月 14, 2020 0

1.题目描述

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

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

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

如果 d 的值为 1，深度 d - 1 不存在，则创建一个新的根节点 v，原先的整棵树将作为 v 的左子树。
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
30
31
32
33
34
35
36
37
38
39
> 示例 1:
> 
> 输入:
>  二叉树如下所示:
>           4
>        /     
>       2       6
>      /      /
>     3   1   5
> v = 1
> d = 2
> 输出:
>          4
>         /  
>        1    1
>       / 
>      2   6
>     /   /
>    3  1  5
> 
> 示例 2:
> 输入:
>  二叉树如下所示:
>       4
>      /
>     2
>    / 
>   3   1
> v = 1
> d = 3
> 输出:
>        4
>       /
>      2
>     / 
>    1   1
>   / 
>  3   1
>

2.解题思路

3.代码

方法1：递归

public static TreeNode (TreeNode root, int v, int d) {
       TreeNode node = new TreeNode(v);
       
        if(d == 1){
            node.left = root;
            return node;
        }
        //
        if(d == 0){
            node.right = root;
            return node;
        }
        if(root != null && d>1){
            root.left = addOneRow(root.left ,v, d > 2 ? d - 1 : 1);
            root.right = addOneRow(root.right,v, d > 2 ? d - 1 : 0);
        }
        return root;
  }

方法2：

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
      public static TreeNode (TreeNode root, int v, int d) {
        Queue<TreeNode> queue = new LinkedList<>();
        //如果 d 的值为 1，深度 d - 1 不存在，则创建一个新的根节点 v，原先的整棵树将作为 v 的左子树。
        if(d==1){
            TreeNode node = new TreeNode(v);
            node.left = root;
            return node;
        }
        queue.add(root);
        int depth = 1;
        TreeNode temp;
        //计算层数，到达前一层结束
        while (!queue.isEmpty()){
            if(depth == d-1)
                break;
            int size = queue.size();
            while (size-->0){
                temp = queue.remove();
                if(temp.left!=null)
                    queue.add(temp.left);
                if(temp.right!=null)
                    queue.add(temp.right);
            }
            depth++;
        }
        TreeNode parent;
        //分别插入
        while (!queue.isEmpty()){
            parent = queue.remove();
            //将v插到左子树
            temp = new TreeNode(v);
            temp.left = parent.left;
            parent.left = temp;
            //将v插到右子树
            temp = new TreeNode(v);
            temp.right = parent.right;
            parent.right = temp;
        }
        return root;
    }

}

4.提交记录