This is the 15th day of my participation in the August More Text Challenge

Finger Offer 32-ii. Print binary tree II from top to bottom

The title

The binary tree is printed from top to bottom layer, with nodes of the same layer printed from left to right, each layer printed to a row.

For example, given a binary tree: [3,9,20,null,null,15,7],

   3
   / \
  9  20
    /  \
   15   7
Copy the code

Returns the result of its hierarchical traversal:

[[3], [9,20], [15,7]Copy the code

Tip:

  1. The total number of nodes <= 1000

Methods a

Hierarchy traversal: Record the number of elements joining the team each time (CNT), and only the number of elements joining the team before each exit, namely CNT

/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */ class Solution { public List<List<Integer>> levelOrder(TreeNode root) { List<List<Integer>> res = new ArrayList<>(); LinkedList<TreeNode> queue = new LinkedList<>(); if (root == null) return res; int cnt = 1; queue.addLast(root); while(queue.size() > 0) { int k = 0; ArrayList<Integer> path = new ArrayList<>(); while((cnt --) > 0) { TreeNode cur = queue.getFirst(); path.add(cur.val); queue.removeFirst(); if (cur.left ! = null) { queue.addLast(cur.left); k ++; } if (cur.right ! = null) { queue.addLast(cur.right); k ++; } } res.add(path); cnt = k; } return res; }}Copy the code

Time complexity: O(n)

Space complexity: O(n)

Finger Offer 32-iii. Print binary tree III from top to bottom

The title

Implement a function to print a binary tree in glyph order, that is, the first line is printed from left to right, the second line is printed from right to left, the third line is printed from left to right, and so on.

For example, given a binary tree: [3,9,20,null,null,15,7],

    3
   / \
  9  20
    /  \
   15   7
Copy the code

Returns the result of its hierarchical traversal:

[[3], [20,9], [15,7]Copy the code

Methods a

On the basis of finger Offer 32-iii. Print binary tree II from top to bottom, determine if the current layer needs to add elements in reverse.

/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */ class Solution { public List<List<Integer>> levelOrder(TreeNode root) { List<List<Integer>> res = new ArrayList<>(); LinkedList<TreeNode> queue = new LinkedList<>(); if (root == null) return res; int cnt = 1, flag = 0; queue.addLast(root); while(queue.size() > 0) { int k = 0; LinkedList<Integer> path = new LinkedList<>(); while((cnt --) > 0) { TreeNode cur = queue.getFirst(); if ((flag & 1) == 0) path.addLast(cur.val); else path.addFirst(cur.val); queue.removeFirst(); if (cur.left ! = null) { queue.addLast(cur.left); k ++; } if (cur.right ! = null) { queue.addLast(cur.right); k ++; } } res.add(path); cnt = k; flag ++; } return res; }}Copy the code

Time complexity: O(n)

Space complexity: O(n)