이진 트리가 있다고 가정합니다. 바이너리 트리에서 가장 긴 경로를 찾아야 합니다.
따라서 입력이 다음과 같으면
가장 긴 연속 시퀀스가 [2, 3, 4, 5, 6]이므로 출력은 5가 됩니다.
이 문제를 해결하기 위해 다음 단계를 따릅니다. −
- 루트가 null이면
- 0을 반환
- 최대 경로:=0
- helper() 함수를 정의합니다. 노드가 필요합니다.
- inc :=1, dec :=1
- 노드의 왼쪽이 null이 아니면
- [left_inc, left_dec] :=도우미(노드 왼쪽)
- 그렇지 않으면
- [left_inc, left_dec] :=[0, 0]
- 노드의 권한이 null이 아니면
- [right_inc, right_dec] :=도우미(노드 오른쪽)
- 그렇지 않으면
- [right_inc, right_dec] :=[0, 0]
- 노드의 왼쪽이 null이 아니고 노드의 값 - 노드의 왼쪽의 값이 1과 같으면
- inc :=최대 inc 및 (left_inc + 1)
- 그렇지 않고 노드의 왼쪽이 null이 아니고 노드의 값 - 노드의 왼쪽의 값이 -1과 같을 때
- dec :=dec의 최대값 및 (left_dec + 1)
- 노드의 오른쪽이 null이 아니고 노드의 값 - 노드의 오른쪽 값이 1과 같으면
- inc :=최대 inc 및 (right_inc + 1)
- 그렇지 않고 노드의 오른쪽이 null이 아니고 노드의 값 - 노드의 오른쪽의 값이 -1과 같을 때
- dec :=dec의 최대값 및 (right_dec + 1)
- 노드의 왼쪽이 null이 아니고 노드의 오른쪽이 null이 아니고 노드의 왼쪽의 값이 1과 같고 노드의 값이 1인 경우 노드의 오른쪽의 값이 1이면
- maxPath :=maxPath의 최대값 및 (left_dec + right_inc + 1)
- 노드 노드의 왼쪽이 null이 아니고 노드의 오른쪽이 null이 아니며 노드의 왼쪽 값이 -1과 같으면
- maxPath :=maxPath의 최대값 및 (left_inc + right_dec + 1)
- maxPath :=maxPath, inc 및 dec의 최대값
- 주식회사, 12월 반환
- 기본 방법에서 다음을 수행합니다.
- 도우미(루트)
- maxPath 반환
이해를 돕기 위해 다음 구현을 살펴보겠습니다. −
예시
class TreeNode: def __init__(self, data, left = None, right = None): self.val = data self.left = left self.right = right def print_tree(root): if root is not None: print_tree(root.left) print(root.val, end = ', ') print_tree(root.right) class Solution: def solve(self, root): if not root: return 0 self.maxPath = 0 def helper(node): inc, dec = 1, 1 if node.left: left_inc, left_dec = helper(node.left) else: left_inc, left_dec = 0, 0 if node.right: right_inc, right_dec = helper(node.right) else: right_inc, right_dec = 0, 0 if node.left and node.val - node.left.val == 1: inc = max(inc, left_inc + 1) elif node.left and node.val - node.left.val == -1: dec = max(dec, left_dec + 1) if node.right and node.val - node.right.val == 1: inc = max(inc, right_inc + 1) elif node.right and node.val - node.right.val == -1: dec = max(dec, right_dec + 1) if (node.left and node.right and node.left.val - node.val == 1 and node.val - node.right.val == 1): self.maxPath = max(self.maxPath, left_dec + right_inc + 1) elif (node.left and node.right and node.left.val - node.val == -1 and node.val - node.right.val == -1): self.maxPath = max(self.maxPath, left_inc + right_dec + 1) self.maxPath = max(self.maxPath, inc, dec) return inc, dec helper(root) return self.maxPath ob = Solution() root = TreeNode(3) root.left = TreeNode(2) root.right = TreeNode(4) root.right.left = TreeNode(5) root.right.right = TreeNode(9) root.right.left.left = TreeNode(6) print(ob.solve(root))
입력
root = TreeNode(3) root.left = TreeNode(2) root.right = TreeNode(4) root.right.left = TreeNode(5) root.right.right = TreeNode(9) root.right.left.left = TreeNode(6)
출력
5