이진 트리가 있다고 가정합니다. 해당 트리의 선주문 순회를 반환해야 합니다. 트리가 다음과 같다면 -
그러면 선주문 순회는 [3,9,20,15,7]
이 됩니다.이 문제를 해결하기 위해 다음 단계를 따릅니다. −
- res 및 st라는 빈 목록을 만듭니다.
- 노드:=루트
- 노드 또는 st가 비어 있지 않은 동안
- 노드가 null이 아닌 경우
- 노드의 val을 res에 삽입하고 노드를 st에 삽입하고 node :=노드의 왼쪽으로 설정
- temp :=st의 마지막 요소, st의 마지막 요소 삭제
- 임시 권한이 있는 경우
- 노드:=임시의 오른쪽
- 노드가 null이 아닌 경우
- 반환 결과
이해를 돕기 위해 다음 구현을 살펴보겠습니다. −
예
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): temp.left = TreeNode(data) break else: que.append(temp.left) if (not temp.right): temp.right = TreeNode(data) 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 preorderTraversal(self, root): res = [] st = [] node = root while node or st: while node: if node.data != None: res.append(node.data) st.append(node) node = node.left temp = st[-1] st.pop() if temp.right: node = temp.right return res ob1 = Solution() head = make_tree([3,9,20,None,None,15,7]) print(ob1.preorderTraversal(head))
입력
[3,9,20,null,null,15,7]
출력
[3, 9, 20, 15, 7]