当前位置：网站首页>Detailed sequence traversal of leetcode102 binary tree

Give you the root node of the binary tree root , Returns the Sequence traversal . （ That is, layer by layer , Access all nodes from left to right ）.

Topic analysis

It is known that ： Root node of binary tree

Purpose ： Sequence traversal

requirement ： Access the binary tree from left to right

Example

Example 1

 Input ：root = [3,9,20,null,null,15,7]
 Output ：[[3],[9,20],[15,7]]

Example 2

 Input ：root = [1]
 Output ：[[1]]

Example 3

 Input ：root = []
 Output ：[]

analysis

Breadth first search

For example 1, The binary tree has a total of 3 layer , Sequence traversal needs to traverse the first layer to get subsets [3], Then traverse the second layer to get a subset [9,20], Finally, traverse the last layer to get a subset [15,7]. about Leetcode94- Middle order traversal of binary trees The general direction of traversal in this problem is from top to bottom , But the output is from bottom to top , Because you need to find the leftmost node from top to bottom , Then output from the leftmost node once from top to bottom , This satisfies the first in and last out characteristics of the stack , So use the stack method to do the problem . And this problem is traversal layer by layer , That is, traverse from top to bottom , And output from top to bottom , This satisfies the idea of queue first in first out , So we can use queues to do this problem .

First initialize three variables , among res Store the subset traversed by each layer ,size Is the number of nodes in each layer ,queue For queue

When traversing the first layer ,size=1, The nodes 3 Join the queue , here size=1, Then only one element is taken from the queue , Element 3, Put it in the result set

here , The nodes 3 The left and right children joined the queue ,size=2 , When you're out of the team , First out 9, pawn out 9 View the node after 9 Have you left or right children , If so, then join the team , If not 20, because size=2, So only 2 Elements .

Finally join the team 15 and 7, Then go out of the team one by one

Depth-first search

Depth first search traverses the binary tree from top to bottom , So this is incompatible with the problem of layer by layer traversal , But since depth first search is traversal from top to bottom, elements can be classified according to layers , At this point, you need to determine which layer each element belongs to , And put the element into the subset of the corresponding layer .

For example, for the following binary tree , A total of 3 layer , Then his result set must contain 3 A subset of , Each subset contains elements of each layer

First, traverse the first layer, that is root node 1, node 1 Belong to 0 Layer nodes , So will 3 Put in a subset 0 in , Then traverse to the node 2, And nodes 2 Belong to 1 layer , Will 2 Put in a subset 1 in , Then traverse to the node 4, node 4 Belong to 2 layer , Will 4 Put in a subset 2, Proceed in sequence until all nodes are traversed

Code

Breadth first search

class Solution:
    def levelOrder(self, root: TreeNode) -> List[List[int]]:
        result = []
        if root is None:
            return result

        q = deque([])  #  Create a queue 
        q.append(root)  #  Add the root node to the queue 
        while len(q) > 0:
            size = len(q)
            ls = []  #  Used to store the nodes traversed by each layer 
            while size > 0:
                cur = q.popleft()
                ls.append(cur.val)
                if cur.left is not None:
                    q.append(cur.left)
                if cur.right is not None:
                    q.append(cur.right)
                size = size-1
            result.append(ls[:])
        return result

Depth-first search

class Solution:
    def levelOrder(self, root: TreeNode) -> List[List[int]]:
        result = []
        if root is None:
            return result

        self.dfs(root, result, 0)
        return result
    
    def dfs(self, node, result, level):
        if node is None:
            return

        if level > len(result)-1:
            result.append([])  #  Talk about the price gap subset to the result set , Used to store the elements of the current layer 

        result[level].append(node.val)

        if node.left is not None:
            self.dfs(node.left, result, level+1)
        if node.right is not None:
            self.dfs(node.right, result, level+1)

原网站

版权声明
本文为[Aries by]所创，转载请带上原文链接，感谢
https://yzsam.com/2022/205/202207240853292168.html