二叉树层次遍历

例题

# 使用队列
class Solution:
    def levelOrder(self, root: Optional[TreeNode]) -> List[List[int]]:
        if root is None:
            return []
        ans=[]
        q=deque([root])
        while q:
            value=[]
            l=len(q)
            for i in range(l):
                node=q.popleft()
                value.append(node.val)
                if node.left:
                    q.append(node.left)
                if node.right:
                    q.append(node.right)
            ans.append(value)
        return ans

# 使用队列，加一个奇偶层判断
class Solution:
    def zigzagLevelOrder(self, root: Optional[TreeNode]) -> List[List[int]]:
        if root is None:
            return []
        ans=[]
        q=deque([root])
        even=False
        while q:
            value=[]
            l=len(q)
            for i in range(l):
                node=q.popleft()
                value.append(node.val)
                if node.left:
                    q.append(node.left)
                if node.right:
                    q.append(node.right)
            ans.append(value[::-1] if even else value)
            even=not even
        return ans

# 可以先层次遍历，返回最后一行的第一个节点的值
class Solution:
    def findBottomLeftValue(self, root: Optional[TreeNode]) -> int:
        if root is None:
            return []
        ans=[]
        q=deque([root])
        while q:
            value=[]
            for _ in range(len(q)):
                node=q.popleft()
                value.append(node.val)
                if node.left:
                    q.append(node.left)
                if node.right:
                    q.append(node.right)
            ans.append(value)
        return ans[-1][0]

# 可以从右往左层次遍历，返回最后一个节点的值
class Solution:
    def findBottomLeftValue(self, root: Optional[TreeNode]) -> int:
        q = deque([root])
        while q:
            node = q.popleft()
            if node.right: q.append(node.right)
            if node.left:  q.append(node.left)
        return node.val