题解 | #输出二叉树的右视图#
输出二叉树的右视图
http://www.nowcoder.com/practice/c9480213597e45f4807880c763ddd5f0
先建树再搜索
class Solution:
def solve(self , xianxu: List[int], zhongxu: List[int]) -> List[int]:
# write code here
max_depth = 0
def dps(xian,zhong,depth):
print(xian,zhong,depth)
nonlocal max_depth
if not xian or not zhong:
return
node_val=xian[0]
root = TreeNode(node_val)
for i in range(len(zhong)):
if zhong[i]==node_val:
root.left = dps(xian[1:i+1],zhong[:i],depth+1)
root.right = dps(xian[i+1:],zhong[i+1:],depth+1)
break
max_depth = max(max_depth, depth)
return root
root = dps(xianxu,zhongxu,1)
print(max_depth)
stack=[root]
d=1
res = []
while( d <=max_depth):
u=[]
a = stack[-1]
while(stack):
b = stack.pop()
if b.right:
u.append(b.right)
if b.left:
u.append(b.left)
res.append(a.val)
d+=1
stack = u[::-1]
return res
