【LeetCode】102. Sequence traversal of binary tree

1 subject

Hierarchical output of binary tree .

2 thought

A common way to solve this problem is to use bfs Write , But sometimes the interviewer asks you to do something dfs edition , So here we use dfs Achieve it . But it also needs the help of the amount of space .

3 Code

# 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
from collections import defaultdict

class Solution:
    def levelOrder(self, root: TreeNode) -> List[List[int]]:
        if root is None:
            return []
        res = defaultdict(list)
        self.dfs(root,0,res) #  The initial height is 0
        return [ val for key,val in res.items()]            

    # height  Indicates the height of the current node 
    def dfs(self,root,height,res):
        #  Put in value 
        res[height].append(root.val) 

        if root.left is not None:
            self.dfs(root.left,height+1,res)
        
        if root.right is not None:
            self.dfs(root.right,height+1,res)