이진 트리가 있다고 가정하고 트리에서 모든 수준의 최대 너비를 찾아야 합니다. 여기서 레벨의 너비는 맨 왼쪽 노드와 맨 오른쪽 노드 사이에 담을 수 있는 노드의 수입니다.
따라서 입력이
그러면 출력은 2
가 됩니다.이 문제를 해결하기 위해 다음 단계를 따르겠습니다-
-
맵 생성 d, 최소값과 최대값을 유지하기 위해 최소값은 초기에 무한대이고 최대값은 0입니다.
-
dfs() 함수를 정의합니다. 이것은 뿌리를 내릴 것입니다. pos :=0, depth :=0
-
루트가 null이면 반환하지 않음
-
d[깊이, 0] =d[깊이, 0] 및 pos
의 최소값 -
d[깊이, 1] =최대 d[깊이,1] 및 pos
-
dfs(노드 왼쪽, 2*pos, 깊이+1)
-
dfs(노드 오른쪽, 2*pos+1, 깊이+1)
-
기본 방법에서 다음을 수행하십시오-
-
dfs(루트)
-
mx:=0
-
d의 모든 값 목록에 있는 각 최소-최대 쌍에 대해 수행
-
왼쪽 :=최소, 오른쪽 :=최대
-
mx:=최대 mx, 오른쪽 왼쪽+1
-
-
MX를 반환
이해를 돕기 위해 다음 구현을 살펴보겠습니다. −
예
from collections import defaultdict class TreeNode: def __init__(self, data, left = None, right = None): self.data = data self.left = left self.right = right class Solution: def solve(self, root): d=defaultdict(lambda: [1e9,0]) def dfs(node, pos=0, depth=0): if not node: return d[depth][0]=min(d[depth][0],pos) d[depth][1]=max(d[depth][1],pos) dfs(node.left,2*pos,depth+1) dfs(node.right,2*pos+1,depth+1) dfs(root) mx=0 for interval in d.values(): l,r=interval mx=max(mx,r-l+1) return mx ob = Solution() root = TreeNode(5) root.left = TreeNode(1) root.right = TreeNode(9) root.right.left = TreeNode(7) root.right.right = TreeNode(10) root.right.left.left = TreeNode(6) root.right.left.right = TreeNode(8) print(ob.solve(root))
입력
root = TreeNode(5) root.left = TreeNode(1) root.right = TreeNode(9) root.right.left = TreeNode(7) root.right.right = TreeNode(10) root.right.left.left = TreeNode(6) root.right.left.right = TreeNode(8)
출력
2