二叉树遍历

二叉树先序遍历(leetcode No.144):

普通，常用版，递归

 1 # Definition for a binary tree node.
 2 # class TreeNode:
 3 #     def __init__(self, x):
 4 #         self.val = x
 5 #         self.left = None
 6 #         self.right = None
 7 
 8 class Solution:
 9     def preorderTraversal(self, root: TreeNode) -> List[int]:
10         if not root:
11             return []
12         path=[]
13         def preorder(root):
14             if root:
15                path.append(root.val)
16                preorder(root.left)
17                preorder(root.right)
18             return 
19         preorder(root)
20         return path

一行解决

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

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

迭代方式

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

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

中序遍历

迭代，每次都先将节点移到树的左下角

 1 # Definition for a binary tree node.
 2 # class TreeNode:
 3 #     def __init__(self, x):
 4 #         self.val = x
 5 #         self.left = None
 6 #         self.right = None
 7 
 8 class Solution:
 9     def inorderTraversal(self, root: TreeNode) -> List[int]:
10         if not root:
11             return []
12         stack=[]
13         path=[]
14         node=root
15         while stack or node:
16             while node:
17                 stack.append(node)
18                 node=node.left
19             node=stack.pop()
20             path.append(node.val)
21             node=node.right
22         return path

递归

 1 # Definition for a binary tree node.
 2 # class TreeNode:
 3 #     def __init__(self, x):
 4 #         self.val = x
 5 #         self.left = None
 6 #         self.right = None
 7 
 8 class Solution:
 9     def inorderTraversal(self, root: TreeNode) -> List[int]:
10         if not root:
11             return []
12         path=[]
13         def inorder(root):
14             if root.left:
15                 inorder(root.left)
16             path.append(root.val)
17             if root.right:
18                 inorder(root.right)
19             return 
20         inorder(root)
21         return path

后序遍历

迭代

 1 class Solution:
 2     def postorderTraversal(self, root: TreeNode) -> List[int]:
 3         if not root:
 4             return []
 5         stack=[root]
 6         path=[]
 7         #node=root
 8         while stack:
 9             #node=stack.pop()
10             node=stack.pop()
11             path.append(node.val)
12             if node.left:
13                 stack.append(node.left)
14             if node.right:
15                 stack.append(node.right)
16         
17         return path[::-1]

 1 # Definition for a binary tree node.
 2 # class TreeNode:
 3 #     def __init__(self, val=0, left=None, right=None):
 4 #         self.val = val
 5 #         self.left = left
 6 #         self.right = right
 7 class Solution:
 8     def postorderTraversal(self, root: TreeNode) -> List[int]:
 9         if not root:
10             return []
11         stack=[]
12         path=[]
13         node=root
14         while stack or node:
15             while node:
16                 stack.append(node)
17                 path.append(node.val)
18                 node=node.right
19             node=stack.pop()
20             node=node.left
21         return path[::-1]

递归

class Solution:
    def postorderTraversal(self, root: TreeNode) -> List[int]:
        path=[]
        def postorder(root):
            if root:
                if root.left:
                    postorder(root.left)
                if root.right:
                    postorder(root.right)
                path.append(root.val)
            return 
        postorder(root)
        return path

层序遍历

BFS

 1 # Definition for a binary tree node.
 2 # class TreeNode:
 3 #     def __init__(self, x):
 4 #         self.val = x
 5 #         self.left = None
 6 #         self.right = None
 7 
 8 class Solution:
 9     def levelOrder(self, root: TreeNode) -> List[List[int]]:
10         if not root:
11             return []
12         stack=collections.deque([root])
13         path=[]
14         while stack:
15             size=len(stack)
16             lists=[]
17             for _ in range(size):
18                 node=stack.popleft()
19                 lists.append(node.val)
20                 if node.left:
21                     stack.append(node.left)
22                 if node.right:
23                     stack.append(node.right)
24             path.append(lists[:])
25         return path

DFS

 1 class Solution:
 2     def levelOrder(self, root: TreeNode) -> List[List[int]]:
 3 
 4         def dfs(root,level,res):
 5             if len(res)==level :res.append([])
 6             res[level].append(root.val)
 7             if root.left: dfs(root.left,level+1,res)
 8             if root.right: dfs(root.right,level+1,res)
 9             return res
10         if not root:
11             return []
12         res=dfs(root,0,[])
13         return res