623. Add One Row to Tree

发表于 | 分类于 | 0 Comments |

623. Add One Row to Tree

题目描述

Given the root of a binary tree, then value v and depth d, you need to add a row of nodes with value v at the given depth d. The root node is at depth 1.

The adding rule is: given a positive integer depth d, for each NOT null tree nodes N in depth d-1, create two tree nodes with value v as N’s left subtree root and right subtree root. And N’s original left subtree should be the left subtree of the new left subtree root, its original right subtree should be the right subtree of the new right subtree root. If depth d is 1 that means there is no depth d-1 at all, then create a tree node with value v as the new root of the whole original tree, and the original tree is the new root’s left subtree.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
Example 1:
Input: 
A binary tree as following:
       4
     /   \
    2     6
   / \   / 
  3   1 5   
v = 1
d = 2
Output: 
       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
Example 2:
Input: 
A binary tree as following:
      4
     /   
    2    
   / \   
  3   1    
v = 1
d = 3
Output: 
      4
     /   
    2
   / \    
  1   1
 /     \  
3       1

Note:
The given d is in range [1, maximum depth of the given tree + 1].
The given binary tree has at least one tree node.

题目大意

给定一个二叉树的根，然后是value v和depth d，你需要在给定的深度d中添加一个值为v的节点行，根节点位于深度1。

给定一深度d，二叉树root,添加规则如下:

  • 深度为d - 1的目标节点，创建两个值为v的节点，作为目标节点的左节点，记为vLeft，和右节点，记为vRight。
  • 目标节点的左子树应该是vLeft的左子树，目标节点的原右子树应该是vRight的右子树。
  • 如果depth d为1，则表示没有深度d - 1，那么创建一个值为v的节点作为root的新根，而root是新根的左子树。

    解题思路

    递归，层序遍历。
    如果d为1，则将v作为根节点返回。
    如果d为2，则将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
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     public var val: Int
 *     public var left: TreeNode?
 *     public var right: TreeNode?
 *     public init(_ val: Int) {
 *         self.val = val
 *         self.left = nil
 *         self.right = nil
 *     }
 * }
 */
class Solution {
    func addOneRow(_ root: TreeNode?, _ v: Int, _ d: Int) -> TreeNode? {
        guard let tree = root else { return nil }
        if d == 1 {
            let node = TreeNode(v)
            node.left = tree
            return node
        }
        if d == 2 {
            let (left, right) = (tree.left, tree.right)
            let (vLeft, vRight) = (TreeNode(v), TreeNode(v))
            vLeft.left = left
            vRight.right = right
            tree.left = vLeft
            tree.right = vRight
            return tree
        }
        addOneRow(tree.left, v, d - 1)
        addOneRow(tree.right, v, d - 1)
        return tree
    }
}
0%