题解：二叉树相关问题及题解（Python）

一、前序遍历
1.1 递归

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

1.2 栈

class Solution:
    def preorderTraversal(self , root: TreeNode) -> List[int]:
        if not root:
            return []
        res = []
        stack = [root]
        while stack:
            node = stack[-1]
            stack = stack[:-1]
            res.append(node.val)
            if node.right:
                stack.append(node.right)
            if node.left:
                stack.append(node.left)
        return res

二、中序遍历
2.1 递归

class Solution:
    def inorder(self, root, res):
        if not root:
            return 
        self.inorder(root.left,res)
        res.append(root.val)
        self.inorder(root.right,res)
    def inorderTraversal(self , root: TreeNode) -> List[int]:
        # write code here 
        res = []
        self.inorder(root, res)
        return res

2.2 栈

class Solution:
    def inorderTraversal(self , root: TreeNode) -> List[int]:
        # write code here 
        res = []
        stack = []
        while stack or root:
            while root:
                stack.append(root)
                root = root.left
            root = stack[-1]
            stack = stack[:-1]
            res.append(root.val)
            root = root.right
        return res

三、后序遍历
3.1 递归

class Solution:
    def postorderTraversal(self , root: TreeNode) -> List[int]:
        if not root:
            return []
        res, stack = [],[]
        pre = None
        while root or stack:
            while root:
                stack.append(root)
                root = root.left
            node = stack[-1]
            stack = stack[:-1]
            if not node.right or  node.right is pre:
                res.append(node.val)
                pre = node
            else:
                stack.append( node)
                root  = node.right
        return res

3.2 栈

class Solution:
    def postorderTraversal(self , root: TreeNode) -> List[int]:
        # write code here
        res, stack = [], []
        pre = None
        while root or stack:
            while root:
                stack.append(root)
                root = root.left
            root = stack[-1]
            stack = stack[:-1]
            if not root.right or root.right is pre:
                res.append(root.val)
                pre = root
            else:
                stack.append(root)
                root = root.right
        return res

四、层序遍历
4.1 递归

class Solution:
    res = []
    def traverse(self, root, depth):
        if not root:
            return 
        if len(self.res) < depth:
            row = []
            row.append(root.val)
            self.res.append(row)
        else:
            row = self.res[depth-1]
            row.append(root.val)
        self.traverse(root.left, depth+1)
        self.traverse(root.right, depth+1)
    def levelOrder(self , root: TreeNode) -> List[List[int]]:
        if not root:
            return []
        self.traverse(root,1)
        return self.res

4.2 栈

class Solution:
    def levelOrder(self , root: TreeNode) -> List[List[int]]:
        if not root:
            return []
        res = []
        queue = [root]
        while queue:
            next_layer_node = []
            row = []
            while queue:
                root = queue[0]
                queue = queue[1:]
                row.append(root.val)
                if root.left:
                    next_layer_node.append(root.left)
                if root.right:
                    next_layer_node.append(root.right)
            queue = next_layer_node
            res.append(row)
        return res