leetcode 144 145 94

二叉树遍历

前序遍历

非递归
class Solution:
    def preorderTraversal(self, root: TreeNode) -> List[int]:
        res = []
        stack = []
        if not root:
            return res
        stack.append(root)
        
        while stack:
            item = stack.pop()
            res.append(item.val)
            if item.right:
                stack.append(item.right)
            if item.left:
                stack.append(item.left)
        return res
递归
class Solution:
    def postorderTraversal(self, root: TreeNode) -> List[int]:
        res = []
        def dfs(root):
            if not root:
                return
            res.append(root.val)
            dfs(root.left)
            dfs(root.right)
        dfs(root)
        return res

中序遍历

非递归
class Solution:
    def inorderTraversal(self, root: TreeNode) -> List[int]:
        res = []
        stack = []
        
        while stack or root:
            while root:
                stack.append(root)
                root = root.left
            root = stack.pop()
            res.append(root.val)
            root = root.right
        return res
递归
class Solution:
    def postorderTraversal(self, root: TreeNode) -> List[int]:
        res = []
        def dfs(root):
            if not root:
                return
            dfs(root.left)
            res.append(root.val)
            dfs(root.right)
        dfs(root)
        return res

后序遍历

非递归
class Solution:
    def postorderTraversal(self, root: TreeNode) -> List[int]:
        res = []
        stack = []
        if not root: return res
        stack.append(root)
        while stack:
            item = stack.pop()
            res.append(item.val)
            if item.left:
                stack.append(item.left)
            if item.right:
                stack.append(item.right)
        
        return reversed(res)

递归
class Solution:
    def postorderTraversal(self, root: TreeNode) -> List[int]:
        res = []
        def dfs(root):
            if not root:
                return
            dfs(root.left)
            dfs(root.right)
            res.append(root.val)
        dfs(root)
        return res