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

This article to share with you is about how to carry out python binary tree level traversal, Xiaobian feel quite practical, so share to everyone to learn, I hope you can read this article after some harvest, not much to say, follow Xiaobian to see it.

Given a binary tree, return the node values traversed hierarchically. (i.e. visit all nodes from left to right, layer by layer).

For example:

Given binary tree: [3,9,20,null,null,15,7],

3

/ \

9 20

/ \

15 7

Returns its hierarchical traversal results:

[

[3],

[9,20],

[15,7]

]

Answer:

1public List levelOrder1(TreeNode root) {

2 Queue queue = new LinkedList();

3 List wrapList = new LinkedList();

4 if (root == null)

5 return wrapList;

6 queue.offer(root);

7 while (! queue.isEmpty()) {

8 int levelNum = queue.size();

9 List subList = new LinkedList();

10 for (int i = 0; i

< levelNum; i++) { 11 if (queue.peek().left != null) 12 queue.offer(queue.peek().left); 13 if (queue.peek().right != null) 14 queue.offer(queue.peek().right); 15 subList.add(queue.poll().val); 16 } 17 wrapList.add(subList); 18 } 19 return wrapList; 20} 解析： LinkedList是个链表，先进先出，levelNum是每一层的节点数量，一层一层的遍历，代码没什么难度，下面再来看一种递归的写法 1public List levelOrder(TreeNode root) { 2 List res = new ArrayList(); 3 levelHelper(res, root, 0); 4 return res; 5} 6 7public void levelHelper(List res, TreeNode root, int height) { 8 if (root == null) return; 9 if (height >

= res.size()) {

10 res.add(new LinkedList());

11 }

12 res.get(height).add(root.val);

13 levelHelper(res, root.left, height + 1);

14 levelHelper(res, root.right, height + 1);

15}

Height is actually equivalent to the hierarchy, height>=res.size() means that you have reached the next level, so you need to create a new list.

The above is how to carry out the hierarchical traversal of python binary tree, Xiaobian believes that some knowledge points may be seen or used in our daily work. I hope you can learn more from this article. For more details, please follow the industry information channel.

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.