题目描述

给定一个二叉树，根节点为第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

示例 2:

输入:
二叉树如下所示:
4
/
2
/ \
3 1

v = 1

d = 3

输出:
4
/
2
/ \
1 1
/ \
3 1
注意:

输入的深度值 d 的范围是：[1，二叉树最大深度 + 1]。
输入的二叉树至少有一个节点。

题目地址
中文版
英文版

代码实现

class Solution(object):
    def addOneRow(self, root, v, d):
        """
        :type root: TreeNode
        :type v: int
        :type d: int
        :rtype: TreeNode
        """
        if d<=0:
            return root
        if d==1:
            pre = TreeNode(v)
            pre.left = root
            return pre
        queue = [root]
        for _ in xrange(2,d):
            size = len(queue)
            for _ in xrange(size):
                node = queue.pop(0)
                if node.left:
                    queue.append(node.left)
                if node.right:
                    queue.append(node.right)       
        for n in queue:
            t1 = TreeNode(v)
            t2 = TreeNode(v)
            t1.left = n.left
            n.left = t1
            t2.right = n.right
            n.right = t2
        return root
                                                     

递归实现

class Solution(object):
    def addOneRow(self, root, v, d):
        """
        :type root: TreeNode
        :type v: int
        :type d: int
        :rtype: TreeNode
        """
        if d<=0:
            return root
        if d==1:
            pre = TreeNode(v)
            pre.left = root
            return pre
        self.index = d-2
        def recursion(root,index):
            if not root:
                return
            if index == 0:
                t1 = TreeNode(v)
                t2 = TreeNode(v)
                t1.left = root.left
                root.left = t1
                t2.right = root.right
                root.right = t2
                return
            recursion(root.left,index-1)
            recursion(root.right,index-1)
        recursion(root,d-2)
        return root
                                                            

3 次阅读