두 갈래 트리가 두루 다니는python 구현: 귀속과 비귀속

두 갈래 트리가 두루 다니는python 구현: 귀속과 비귀속

선착순 반복

중순 스트리밍

후순 반복

먼저 순서대로 두루 다니다.

창고를 이용해서 팝 다음에push 서브 트리에

class Solution:
    def preorderTraversal(self, root):
        """
        :type root: TreeNode
        :rtype: List[int]
        """
        if root == None:
            return []
        
        res = []
        stack = [root]
        while stack:
            current = stack.pop()
            if current:
                res.append(current.val)
                stack.append(current.right)
                stack.append(current.left)
        return res

class Solution:
    def preorderTraversal(self, root):
        """
        :type root: TreeNode
        :rtype: List[int]
        """

        if root == None:
            return []
        res = []
        res.append(root.val)
        res += self.preorderTraversal(root.left)
        res += self.preorderTraversal(root.right)
        
        return res

중순으로 두루 다니다.

class Solution:
    def inorderTraversal(self, root):
    	if root ==None:
            return[]
        res=[]
        res+=self.inorderTraversal(root.left)
        res.append(root.val)
        res+=self.inorderTraversal(root.right)
        return res

창고를 이용하면 뿌리 노드는 사실 왼쪽 나무로 볼 수 있고, 그 다음에push오른쪽 나무로 볼 수 있다.

class Solution:
    def inorderTraversal(self, root):
        """
        :type root: TreeNode
        :rtype: List[int]
        """
        
        if root==None:
            return[]
        stack=[]
        res=[]
        while True:
            while root:
                stack.append(root)
                root=root.left
            if not stack:
                return res
            current=stack.pop()
            res.append(current.val)
            root=current.right
        return res
        

후순이 두루 다니다

선착순과 비교할 수 있다. 선착순은 서브트리push 이전에 루트 노드를 팝업하고 후속은 없다. 또한 tag를 이용하여 좌우 서브트리가 모두 팝업한 후에야 팝업 루트 노드를 팝업할 수 있는지 지시한다.

class Solution:
    def postorderTraversal(self, root):
        """
        :type root: TreeNode
        :rtype: List[int]
        """
        stack = [root]
        res = []
        
        while stack:
            cur = stack[-1]
            if not cur:
                stack.pop()
                continue
            if not cur.left and not cur.right:
                res.append(stack.pop().val)
                continue
            stack.append(cur.right)
            stack.append(cur.left)
            cur.left, cur.right = None, None
        
        return res

class Solution:
    def postorderTraversal(self, root):
        """
        :type root: TreeNode
        :rtype: List[int]
        """
        
        if root == None:
            return []
        res=[]
        res+=self.postorderTraversal(root.left)
        res+=self.postorderTraversal(root.right)
        res.append(root.val)
        return res