遍歴ツリー:反復モードのクリーンアップ反復モード

9680 ワード
algorithm binary tree python テキストリンク
可読性が良く、統一的に適用できるツリー巡りモードが発見されました.
売れないように文字で整理する.
Pre-order
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def preorderTraversal(self, root: TreeNode) -> List[int]:
        ans = []
        stack = [(root, False)]
        
        while stack:
            node, hit = stack.pop()
            
            if node:
                if hit:
                    ans.append(node.val)
                else:
                    stack.append((node.right, False))
                    stack.append((node.left, False))
                    stack.append((node, True))
                    
        return ans
In-order
class Solution:
    def inorderTraversal(self, root: TreeNode) -> List[int]:
        ans = []
        stack = [(root, False)]
        
        while stack:
            node, hit = stack.pop()
            
            if node:
                if hit:
                    ans.append(node.val)
                else:
                    stack.append((node.right, False))
                    stack.append((node, True))
                    stack.append((node.left, False))
                    
        return ans
Post-order
class Solution:
    def postorderTraversal(self, root: TreeNode) -> List[int]:
        ans = []
        stack = [(root, False)]
        
        while stack:
            node, hit = stack.pop()
            
            if node:
                if hit:
                    ans.append(node.val)
                else:
                    stack.append((node, True))
                    stack.append((node.right, False))
                    stack.append((node.left, False))
                    
        return ans
[C]白駿2581号-直角三角形-
[react]13-Hooks:レンダリングアレイ