Shulou(Shulou.com)06/01 Report--

This article mainly introduces "how to realize the hierarchical traversal of Python binary tree". In the daily operation, I believe that many people have doubts about how to realize the hierarchical traversal of Python binary tree. The editor has consulted all kinds of materials and sorted out simple and easy-to-use operation methods. I hope it will be helpful to answer the doubt of "how to realize the hierarchical traversal of Python binary tree". Next, please follow the editor to study!

Title

Given a binary tree, returns a hierarchical traversal of its node value from the bottom up. (that is, traverse from left to right layer by layer from the leaf node to the root node)

For example:

Given binary tree [3pc9pr 20pr nullpr nullpr 15pc7]

3 / 9 20 / 15 7

Returns its bottom-up hierarchy traversal as follows:

[[15] 7], [9] 20], [3] solution ideas: breadth-first search (BFS)

First look at the topic, which requires a bottom-up hierarchical traversal of the return node value. (from the leaf node layer to the root node layer, traverse layer by layer from left to right.)

Then we can find that using the breadth-first search method is the most intuitive, the topic requires bottom-up, here I first use stack storage when I traverse the search from top to bottom, and then reverse order (that is, bottom-up). The specific practices are as follows:

Search from the root node

In each search, determine the number of nodes in the current layer, traverse all the nodes in the current layer, and store the node values of the current layer with a list.

The list of node values of each layer is stored with the stack, and the reverse order is realized later.

The specific code implementation is as follows:

# Definition for a binary tree node.# class TreeNode:# def _ init__ (self, x): # self.val = x # self.left = None# self.right = Nonefrom collections import dequeclass Solution: def levelOrderBottom (self Root: TreeNode)-> list [ans]: if not root: return [] ans = [] stack = [] queue = deque () queue.append (root) while queue: cnt = len (queue) tmp = [] for _ in range (cnt): Node = queue.popleft () if node.left: queue.append (node.left) if node.right: queue.append (node.right) tmp.append (node.val) stack.append (tmp) while Stack: ans.append (stack.pop ()) return ans so far The study on "how to realize the hierarchical traversal of Python binary tree" is over. I hope to be able to solve your doubts. The collocation of theory and practice can better help you learn, go and try it! If you want to continue to learn more related knowledge, please continue to follow the website, the editor will continue to work hard to bring you more practical articles!

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.