이진 트리가 있다고 가정합니다. 반복적 접근을 사용하여 이 트리의 사후 순회를 찾아야 합니다. 트리가 다음과 같다면 -
그러면 출력은 다음과 같습니다. [9,15,7,10,-10]
이 문제를 해결하기 위해 다음 단계를 따릅니다. −
-
루트가 null이면 빈 배열을 반환합니다.
-
ret 배열 생성
-
stack :=[root, 0] 쌍으로 스택 정의
-
스택이 비어 있지 않은 동안 -
-
node :=스택의 맨 위, 스택에서 요소 삭제
-
노드 쌍의 두 번째 값이 0이면
-
현재 :=노드 쌍의 첫 번째 값
-
스택에 쌍(현재, 1) 삽입
-
현재의 권리가 있는 경우 -
-
[현재 오른쪽, 0] 쌍을 스택에 삽입
-
-
전류의 왼쪽이 있는 경우 -
-
[현재의 왼쪽, 0] 쌍을 스택에 삽입
-
-
-
그렇지 않으면 첫 번째 값 노드 쌍의 데이터가 0이 아닌 경우 노드의 첫 번째 값 데이터를 res
에 삽입합니다.
-
-
반환 해상도
예시
더 나은 이해를 위해 다음 구현을 살펴보겠습니다. −
class TreeNode: def __init__(self, data, left = None, right = None): self.data = data self.left = left self.right = right def insert(temp,data): que = [] que.append(temp) while (len(que)): temp = que[0] que.pop(0) if (not temp.left): if data is not None: temp.left = TreeNode(data) else: temp.left = TreeNode(0) break else: que.append(temp.left) if (not temp.right): if data is not None: temp.right = TreeNode(data) else: temp.right = TreeNode(0) break else: que.append(temp.right) def make_tree(elements): Tree = TreeNode(elements[0]) for element in elements[1:]: insert(Tree, element) return Tree class Solution(object): def postorderTraversal(self, root): if not root: return [] res = [] stack = [[root,0]] while stack: node = stack[-1] stack.pop() if node[1]== 0 : current = node[0] stack.append([current,1]) if current.right: stack.append([current.right,0]) if current.left: stack.append([current.left,0]) else: if node[0].data != 0: res.append(node[0].data) return res ob = Solution() root = make_tree([-10,9,10,None,None,15,7]) print(ob.postorderTraversal(root))
입력
[-10,9,10,None,None,15,7]
출력
[9, 15, 7, 10, -10]