目录

1.建树

2.中序遍历

（1）递归

（2）迭代

3.先序遍历

（1）递归

（2）迭代

4.后序遍历

（1）递归

（2）迭代

5.102. 二叉树的层序遍历 - 力扣（LeetCode） (leetcode-cn.com)

6.107. 二叉树的层序遍历 II - 力扣（LeetCode） (leetcode-cn.com)

7.199. 二叉树的右视图 - 力扣（LeetCode） (leetcode-cn.com)

8.637. 二叉树的层平均值 - 力扣（LeetCode） (leetcode-cn.com)

9.429. N 叉树的层序遍历 - 力扣（LeetCode） (leetcode-cn.com)

10.515. 在每个树行中找最大值 - 力扣（LeetCode） (leetcode-cn.com)

11.116. 填充每个节点的下一个右侧节点指针 - 力扣（LeetCode） (leetcode-cn.com)

12.117. 填充每个节点的下一个右侧节点指针 II - 力扣（LeetCode） (leetcode-cn.com)

13.104. 二叉树的最大深度 - 力扣（LeetCode） (leetcode-cn.com)

14.111. 二叉树的最小深度 - 力扣（LeetCode） (leetcode-cn.com)

---

1.建树

很不熟悉类

class TreeNode:
    def __init__(self,value):
        self.value=value
        self.left=None
        self.right=None

2.中序遍历

（1）递归

# 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: Optional[TreeNode]) -> List[int]:
        martix=[]
        def traversal(root):
            if root==None:return
            traversal(root.left)
            martix.append(root.val)
            traversal(root.right)
        traversal(root)
        return martix
            

（2）迭代

# 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 inorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
        result=[]
        if root==None:
            return result
        #左中右
        stack=[]
        cur=root
        while cur or stack:
            if cur:
                stack.append(cur)
                cur=cur.left
            else:
                cur = stack.pop()
                result.append(cur.val)
                cur=cur.right
        return result

3.先序遍历

（1）递归

# 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: Optional[TreeNode]) -> List[int]:
        martix=[]
        def traversal(root):
            if root==None:return
            martix.append(root.val)
            traversal(root.left)
            traversal(root.right)
        traversal(root)
        return martix
            

（2）迭代

# 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: Optional[TreeNode]) -> List[int]:
        result=[]
        if root==None:return result
        stack=[root]
        while stack:
            top=stack.pop()
            result.append(top.val)
            if top.right:
                stack.append(top.right)
            if top.left:
                stack.append(top.left)
        return result

4.后序遍历

（1）递归

# 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 postorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
        martix=[]
        def traversal(root):
            if root==None:return
            traversal(root.left)
            traversal(root.right)
            martix.append(root.val)
        traversal(root)
        return martix

（2）迭代

# 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 postorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
        result=[]
        if root==None:
            return result
        stack=[root]
        while stack:
            top=stack.pop()
            result.append(top.val)
            if top.left:
                stack.append(top.left)
            if top.right:
                stack.append(top.right)
        return result[::-1]

5.102. 二叉树的层序遍历 - 力扣（LeetCode） (leetcode-cn.com)

# 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 levelOrder(self, root: TreeNode) -> List[List[int]]:
        results=[]
        if root==None:
            return results
        from collections import deque
        que=deque([root])
        while que:
            size=len(que)
            result=[]
            for i in range(size):
                top=que.popleft()
                result.append(top.val)
                if top.left:
                    que.append(top.left)
                if top.right:
                    que.append(top.right)
            results.append(result)
        return results

6.107. 二叉树的层序遍历 II - 力扣（LeetCode） (leetcode-cn.com)

# 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 levelOrderBottom(self, root: TreeNode) -> List[List[int]]:
        results=[]
        if root==None:
            return results
        from collections import deque
        que=deque([root])
        while que:
            size=len(que)
            result=[]
            for i in range(size):
                top=que.popleft()
                result.append(top.val)
                if top.left:
                    que.append(top.left)
                if top.right:
                    que.append(top.right)
            results.append(result)
        return results[::-1]

7.199. 二叉树的右视图 - 力扣（LeetCode） (leetcode-cn.com)

# 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 rightSideView(self, root: TreeNode) -> List[int]:
        result=[]
        if root==None:
            return result
        from collections import deque
        que=deque([root])
        while que:
            size=len(que)
            for i in range(size):
                top=que.popleft()
                if i==size-1:
                    result.append(top.val)
                if top.left:
                    que.append(top.left)
                if top.right:
                    que.append(top.right)
        return result

8.637. 二叉树的层平均值 - 力扣（LeetCode） (leetcode-cn.com)

# 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 averageOfLevels(self, root: Optional[TreeNode]) -> List[float]:
        results=[]
        if root==None:
            return results
        from collections import deque
        que=deque([root])
        while que:
            size=len(que)
            result=[]
            for i in range(size):
                top=que.popleft()
                result.append(top.val)
                if top.left:
                    que.append(top.left)
                if top.right:
                    que.append(top.right)
            results.append(sum(result)/size)
        return results

9.429. N 叉树的层序遍历 - 力扣（LeetCode） (leetcode-cn.com)

"""
# Definition for a Node.
class Node:
    def __init__(self, val=None, children=None):
        self.val = val
        self.children = children
"""

class Solution:
    def levelOrder(self, root: 'Node') -> List[List[int]]:
        results=[]
        if root==None:
            return results
        from collections import deque
        que=deque([root])
        while que:
            size=len(que)
            result=[]
            for i in range(size):
                top=que.popleft()
                result.append(top.val)
                for j in range(len(top.children)):
                    que.append(top.children[j])
            results.append(result)
        return results

10.515. 在每个树行中找最大值 - 力扣（LeetCode） (leetcode-cn.com)

# 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 largestValues(self, root: Optional[TreeNode]) -> List[int]:
        results=[]
        if root==None:
            return results
        from collections import deque
        que=deque([root])
        while que:
            size=len(que)
            result=[]
            for i in range(size):
                top=que.popleft()
                result.append(top.val)
                if top.left:
                    que.append(top.left)
                if top.right:
                    que.append(top.right)
            results.append(max(result))
        return results

11.116. 填充每个节点的下一个右侧节点指针 - 力扣（LeetCode） (leetcode-cn.com)

"""
# Definition for a Node.
class Node:
    def __init__(self, val: int = 0, left: 'Node' = None, right: 'Node' = None, next: 'Node' = None):
        self.val = val
        self.left = left
        self.right = right
        self.next = next
"""

class Solution:
    def connect(self, root: 'Optional[Node]') -> 'Optional[Node]':
        results=[]
        if not root:
            return root
        from collections import deque
        que=deque([root])
        while que:
            size=len(que)
            result=[]
            for i in range(size):
                top=que.popleft()
                result.append(top.val)
                if top.left:
                    que.append(top.left)
                if top.right:
                    que.append(top.right)
                if i!=size-1:
                    top.next=que[0]
        return root

12.117. 填充每个节点的下一个右侧节点指针 II - 力扣（LeetCode） (leetcode-cn.com)

代码都一模一样

"""
# Definition for a Node.
class Node:
    def __init__(self, val: int = 0, left: 'Node' = None, right: 'Node' = None, next: 'Node' = None):
        self.val = val
        self.left = left
        self.right = right
        self.next = next
"""

class Solution:
    def connect(self, root: 'Node') -> 'Node':
        results=[]
        if not root:
            return root
        from collections import deque
        que=deque([root])
        while que:
            size=len(que)
            result=[]
            for i in range(size):
                top=que.popleft()
                result.append(top.val)
                if top.left:
                    que.append(top.left)
                if top.right:
                    que.append(top.right)
                if i!=size-1:
                    top.next=que[0]
        return root

13.104. 二叉树的最大深度 - 力扣（LeetCode） (leetcode-cn.com)

# 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 maxDepth(self, root: Optional[TreeNode]) -> int:
        results=[]
        if not root:
            return 0
        from collections import deque
        que=deque([root])
        depth=0
        while que:
            depth+=1
            size=len(que)
            result=[]
            for i in range(size):
                top=que.popleft()
                result.append(top.val)
                if top.left:
                    que.append(top.left)
                if top.right:
                    que.append(top.right)
        return depth

14.111. 二叉树的最小深度 - 力扣（LeetCode） (leetcode-cn.com)

# 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 minDepth(self, root: TreeNode) -> int:
        if not root:
            return 0
        from collections import deque
        que=deque([root])
        depth=0
        while que:
            depth+=1
            size=len(que)
            result=[]
            for i in range(size):
                top=que.popleft()
                if top.left==top.right==None:
                    return depth
                if top.left:
                    que.append(top.left)
                if top.right:
                    que.append(top.right)
        return depth