牛客题霸-求二叉树的层序遍历-Java,Go题解

题目链接

https://www.nowcoder.com/practice/04a5560e43e24e9db4595865dc9c63a3?tpId=117

1. Go语言

   package main
   import . "nc_tools"
   func levelOrder( root *TreeNode ) [][]int {
    var result [][]int
    if root == nil {
         return result
    }
    var queueFather []*TreeNode
    var queueChild []*TreeNode
        // 使用了双队列,如果想要简写的话可以直接使用一个临时队列也OK
    queueFather = append(queueFather,root)
    for len(queueFather) != 0 || len(queueChild) != 0 {
        var queue []int
        for len(queueFather) != 0 {
            item := queueFather[0]
            queue = append(queue, item.Val)
            queueFather = queueFather[1:]
            if item.Left != nil {
                queueChild = append(queueChild, item.Left)
            }
            if item.Right != nil {
                queueChild = append(queueChild, item.Right)
            }
        }
        result = append(result, queue)
        queue = []int{}
        for len(queueChild) != 0 {
            item := queueChild[0]
            queue = append(queue, item.Val)
            queueChild = queueChild[1:]
            if item.Left != nil {
                queueFather = append(queueFather,item.Left)
            }
            if item.Right != nil {
                queueFather = append(queueFather,item.Right)
            }
        }
        if len(queue) != 0{
            result = append(result, queue)
        }
    }
    return result
    // write code here
   }

2. Java

import java.util.*;
public class Solution {
    public ArrayList<ArrayList<Integer>> levelOrder(TreeNode root) {
        LinkedList<TreeNode> queueFather = new LinkedList<>();
        LinkedList<TreeNode> queueChild = new LinkedList<>();
        ArrayList<ArrayList<Integer>> resultList = new ArrayList<>();
        if (root != null) {
            queueFather.add(root);
        }
        while (queueFather.size() > 0 || queueChild.size() > 0) {
            ArrayList<Integer> rowList = new ArrayList<>();
            if (queueFather.size() > 0) {
                while (queueFather.size() > 0) {
                    TreeNode node = queueFather.pop();
                    if (node.left != null) {
                        queueChild.add(node.left);
                    }
                    if (node.right != null) {
                        queueChild.add(node.right);
                    }
                    rowList.add(node.val);
                }
            } else{
                while (queueChild.size() > 0) {
                    TreeNode node = queueChild.pop();
                    if (node.left != null) {
                        queueFather.add(node.left);
                    }
                    if (node.right != null) {
                        queueFather.add(node.right);
                    }
                    rowList.add(node.val);
                }

            }
            resultList.add(rowList);

        }
        return resultList;
    }
}