107. Hierarchical traversal of binary trees II

Given a binary tree, return a bottom-up hierarchical traversal of its node values. (that is, from the layer where the leaf node is located to the layer where the root node is located, layer by layer from left to right)

Such as:

Given a binary tree [3.9.20.null.null.15.7].



    3

   / \

  9  20

    /  \

   15   7

Returns its bottom-up hierarchical traversal as:



[

  [15.7].

  [9.20].

  [3]

]

Copy the code

Method 1: Breadth-first search for BFS

Algorithm idea:

Hierarchical traversal of the tree can be implemented using breadth-first search. The search starts at the root node, traversing all nodes of the same tier at a time, using a list to store the node values of that tier.

If you want to print the node values for each layer from top to bottom, it is straightforward to add the list of node values for that layer to the end of the result list after traversing a layer of nodes. This requires printing the node values for each layer from bottom to top, with a slight modification: After traversing a layer of nodes, add the list of node values for that layer to the head of the result list.

To reduce the time complexity of adding a layer of node values to a list at the head of the result list, the result list can be structured as a linked list with O(1) time complexity.

Reference Code 1:

/ * *

 * Definition for a binary tree node.

 * public class TreeNode {

 *     int val;

 *     TreeNode left;

 *     TreeNode right;

 *     TreeNode(int x) { val = x; }

*}

* /

class Solution {

    // BFS

    public List<List<Integer>> levelOrderBottom1(TreeNode root) {

        List<List<Integer>> res = new ArrayList<>();

        if (root == null) {

            return res;

        }

        // First in, last out

        Queue<TreeNode> queue = new ArrayDeque<>();

        queue.add(root);

        while(! queue.isEmpty()) {

            int size = queue.size();

            List<Integer> subs = new ArrayList<>();

            for (int i = 0; i < size; i++) {

                TreeNode cur = queue.poll();

                subs.add(cur.val);

                if(cur.left ! =null) {

                    queue.add(cur.left);

                }

                if(cur.right ! =null) {

                    queue.add(cur.right);

                }

            }

            res.add(0, subs);

        }

        return res;

    }

}

Copy the code

Complexity analysis:

• Time complexity: O(n), where n is the number of nodes in the binary tree. Each node is accessed once. When the structure of linked list is used in the result list, the time complexity of adding a layer of node values to the head of the result list is O(1), so the total time complexity is O(n).
• Space complexity: O(n), where n is the number of nodes in the binary tree. The space complexity depends on the queue overhead, and the number of nodes in the queue does not exceed N.

Method 2: Depth-first search DFS

Algorithm idea:

DFS implementation is a little bit less intuitive, so we can change the binary tree structure, think of it as a triangle structure and we recursively iterate, putting the elements of the first layer into the first layer array, putting the elements of the second layer into the second layer, and putting the elements of the third layer into the third layer. The fourth of the third level is traversed before 5, so when we put it in the third level array, 4 comes before 5, and 6 comes before 7, so when we put it in the third level array, 6 comes before 7.

The complete traversal process is as follows:Finally, the set is reversed and returned.

Reference Code 2:

/ * *

 * Definition for a binary tree node.

 * public class TreeNode {

 *     int val;

 *     TreeNode left;

 *     TreeNode right;

 *     TreeNode(int x) { val = x; }

*}

* /

class Solution {

    // DFS

    public List<List<Integer>> levelOrderBottom(TreeNode root) {

        List<List<Integer>> res = new ArrayList<>();

        if (root == null) {

            return res;

        }

        dfs(root, res, 1);

        Collections.reverse(res);

        return res;

    }



    private void dfs(TreeNode root, List<List<Integer>> res, int level) {

        if (root == null) {

            return;

        }

        if (level > res.size()) {

            res.add(new ArrayList<>());

        }

        res.get(level - 1).add(root.val);

        dfs(root.left, res, level + 1);

        dfs(root.right, res, level + 1);

    }

}

Copy the code

Complexity analysis:

• Time complexity: O(n), where n is the number of nodes in the binary tree. Recursively, each node is accessed once.
• Space complexity: O(n), the stack space used during recursion

Some pictures from the network, copyright to the original author, delete.Copy the code