Leetcode-102 – Sequence traversal of binary trees

This is the 27th day of my participation in the August Genwen Challenge.More challenges in August

Sequential traversal of binary trees

Given a binary tree, please return the value of the node traversed in order. (That is, layer by layer, all nodes are accessed from left to right).

Examples can be found on the LeetCode website.

Source: LeetCode link: leetcode-cn.com/problems/bi… Copyright belongs to the Collar buckle network. Commercial reprint please contact official authorization, non-commercial reprint please indicate the source.

Solution 1: use queue traversal binary tree

The characteristics of queues are first-in, first-out, so queues are used to traverse binary trees to achieve sequence traversal, and the specific process is as follows:

• First, if root is empty, return the empty List.
• If root is not empty, declare a queue of Nodes, add root to the queue, declare a result, and iterate over nodes as follows:
  • First, count is used to record the number of nodes in the current queue (i.e. the number of nodes in the current tier), and vals is used to record the value of the current node.
  • Remove count nodes from Nodes and place the corresponding values in VALS, and if the left and right children of the current node are not empty, place them in nodes from left to right. Add vals to the result result.
• Repeat through the nodes in Nodes until Nodes is empty.
• Result is the result of the sequence traversal.

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

public class LeetCode_102 {
    /** * traverses the binary tree with queues: queues are first-in, first-out@param root
     * @return* /
    public static List<List<Integer>> levelOrder(TreeNode root) {
        if (root == null) {
            return new ArrayList<>();
        }
        List<List<Integer>> result = new ArrayList<>();
        // Hold the nodes for each row
        Queue<TreeNode> nodes = new LinkedList<>();
        nodes.add(root);
        while(! nodes.isEmpty()) {// Iterate over the data one line at a time
            List<Integer> vals = new ArrayList<>();
            int count = nodes.size();
            while (count > 0) {
                TreeNode curNode = nodes.poll();
                vals.add(curNode.val);
                Queue the left and right children of the current node from left to right
                if(curNode.left ! =null) {
                    nodes.add(curNode.left);
                }
                if(curNode.right ! =null) {
                    nodes.add(curNode.right);
                }
                count--;
            }
            result.add(vals);
        }
        return result;
    }

    public static void main(String[] args) {
        TreeNode root = new TreeNode(3);
        root.left = new TreeNode(9);
        root.right = new TreeNode(20);
        root.right.left = new TreeNode(15);
        root.right.right = new TreeNode(7);

        for (List<Integer> integers : levelOrder(root)) {
            for (Integer integer : integers) {
                System.out.print(integer + ""); } System.out.println(); }}}Copy the code

Modesty helps one to go forward; conceit makes one lag behind.