動機
從bottom重建tree
以後是不是應該整理dfs在tree上的用法?
Problem
Given the root
of a binary tree and two integers val
and depth
, add a row of nodes with value val
at the given depth depth
.
Note that the root
node is at depth 1
.
The adding rule is:
- Given the integer
depth
, for each not Leetcode tree nodecur
at the depthdepth - 1
, create two tree nodes with valueval
ascur
's left subtree root and right subtree root. cur
's original left subtree should be the left subtree of the new left subtree root.cur
's original right subtree should be the right subtree of the new right subtree root.- If
depth == 1
that means there is no depthdepth - 1
at all, then create a tree node with valueval
as the new root of the whole original tree, and the original tree is the new root's left subtree.
Example 1:
Input: root = [4,2,6,3,1,5], val = 1, depth = 2Output: [4,1,1,2,null,null,6,3,1,5]
Example 2:
Input: root = [4,2,null,3,1], val = 1, depth = 3Output: [4,2,null,1,1,3,null,null,1]
Constraints:
- The number of nodes in the tree is in the range
[1, 104]
. - The depth of the tree is in the range
[1, 104]
. -100 <= Node.val <= 100
-105 <= val <= 105
1 <= depth <= the depth of tree + 1
sol
class Solution:
def addOneRow(self, root: Optional[TreeNode], val: int, depth: int, left = True) -> Optional[TreeNode]:
if depth == 0:
return root
elif depth == 1:
ret = TreeNode(val)
(ret.left if left else ret.right) = root
return ret
else:
if not root:
return root
else:
root.left = self.addOneRow(root.left, val, depth-1, True)
root.right = self.addOneRow(root.right, val, depth-1, False)
return root