LeetCode 144 [Binary Tree Preorder Traversal]

2098 단어

원제


두 갈래 나무를 제시하고 노드 값의 앞순서를 되돌려줍니다.
두 갈래 나무 {1,#,2,3}
   1
    \
     2
    /
   3

복귀 [1,2,3]

문제 풀이 사고방식

  • helper 함수 중if root: 즉, 루트가 None이 아니면 부/좌/우로 추가합니다
  • 방법 1, 가장 간단,recursion(no return value)
  • 방법2,divide&conquer(hasreturnvalue)
  • 방법 3, 비귀속, 귀속은 시스템의 창고 공간을 호출하기 때문에 비귀속의 실현은stack이라는 데이터 구조에 사용해야 한다

  • 전체 코드

    # Definition for a binary tree node.
    # class TreeNode(object):
    #     def __init__(self, x):
    #         self.val = x
    #         self.left = None
    #         self.right = None
    
    #  
    class Solution(object):
        def preorderTraversal(self, root):
            """
            :type root: TreeNode
            :rtype: List[int]
            """
            ret = []
            self.RecPreOrderTraversal(root, ret)
            return ret
            
        def RecPreOrderTraversal(self, root, result):
            if root != None: # skip None or Leaf
                result.append(root.val)
                self.RecPreOrderTraversal(root.left, result)
                self.RecPreOrderTraversal(root.right, result)
    
    #  
    class Solution(object):
        def preorderTraversal(self, root):
            """
            :type root: TreeNode
            :rtype: List[int]
            """
            res = []
            if root is None:
                return res
            
            left = self.preorderTraversal(root.left)
            right = self.preorderTraversal(root.right)
            
            res.append(root.val)
            res += left
            res += right
            return res 
    
    #  
    class Solution(object):
        def preorderTraversal(self, root):
            """
            :type root: TreeNode
            :rtype: List[int]
            """
            if root is None:
                return []
            stack = [root]
            preorder = []
            while stack:
                node = stack.pop()
                preorder.append(node.val)
                if node.right:
                    stack.append(node.right)
                if node.left:
                    stack.append(node.left)
            return preorder
    

    좋은 웹페이지 즐겨찾기