이진 트리가 있다고 가정하고 노드와 그 후손 간의 가장 큰 절대 차이를 찾아야 합니다.
따라서 입력이 다음과 같으면
노드 8과 1 사이에 가장 큰 절대 차이가 있으므로 출력은 7이 됩니다.
이 문제를 해결하기 위해 다음 단계를 따릅니다. −
- dfs() 함수를 정의합니다. 노드가 필요합니다.
- 노드가 null이 아니면
- 양수 및 음수 무한대가 있는 목록 반환
- left :=dfs(노드의 왼쪽)
- right :=dfs(노드의 오른쪽)
- res :=(left[0], right[0]의 최소값과 노드 값, left[1], right[1]의 최대값과 노드 값)의 쌍
- ans :=ans의 최대값, (노드 값 - res[0]) 및 (res[1] - 노드 값)
- 반환 결과
- 메인 방법에서 다음을 수행하십시오. -
- ans :=0
- dfs(루트)
- 반환
이해를 돕기 위해 다음 구현을 살펴보겠습니다. −
예시
class TreeNode:def __init__(self, data, left =None, right =None):self.val =data self.left =left self.right =rightclass 솔루션:def solve(self, root):def dfs( node):노드가 아닌 경우:return [float("inf"), float("-inf")] left =dfs(node.left) right =dfs(node.right) res =[min(left[0], right[0], node.val), max(left[1], right[1], node.val)] self.ans =max(self.ans, node.val - res[0], res[1] - node.val) return res self.ans =0 dfs(root) return self.ansob =Solution()root =TreeNode(1)root.left =TreeNode(5)root.right =TreeNode(3)root.right. left =TreeNode(2)root.right.right =TreeNode(8)root.right.left.left =TreeNode(7)root.right.left.right =TreeNode(4)print(ob.solve(root)) 입력
루트 =TreeNode(1)root.left =TreeNode(5)root.right =TreeNode(3)root.right.left =TreeNode(2)root.right.right =TreeNode(8)root.right.left .left =TreeNode(7)root.right.left.right =TreeNode(4)
출력
7