面试题32 - I. 从上到下打印二叉树

题目描述：

从上到下打印出二叉树的每个节点，同一层的节点按照从左到右的顺序打印。

例如:
给定二叉树: [3,9,20,null,null,15,7],

[3,9,20,15,7]

提示：

节点总数 <= 1000

python3 解法：

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution(object):
    def levelOrder(self, root):
        """
        :type root: TreeNode
        :rtype: List[int]
        """
        queue = [root]
        ans = []
        for i in queue:
            if i is not None:
                ans.append(i.val)
                if i.left is not None:
                    queue.append(i.left)
                if i.right is not None:
                    queue.append(i.right)
        return ans

Java解法（ArrayList）：

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public int[] levelOrder(TreeNode root) {
        //如果数是空的，则返回空数组
        if (root == null)
        {
            return new int[0];
        }
        //利用ArrayList结构来存储遍历的所有节点
        ArrayList<TreeNode> list = new ArrayList<>();
        //将根节点添加到list中
        list.add(root);
        int i = 0;
        //遍历list中的节点，直到遍历完所有节点
        while(i < list.size())
        {
            //取出当前遍历节点
            TreeNode node = list.get(i);
            //判断当前节点的左节点是否为空
            if (node.left != null)
            {
                //左子节点不为空，就将其添加到list中
                list.add(node.left);
            }
            //判断当前节点的右节点是否为空
            if(node.right != null)
            {
                //右子节点不为空，就将其添加到list中
                list.add(node.right);
            }
            //遍历的指针向前走一步
            i++;
        }
        //当前list中存储了二叉树的所有节点，依次将节点的值存储到数组中输出
        int size = list.size();
        int[] ans = new int[size];
        for(int j= 0; j < size; j++)
        {
            ans[j] = list.get(j).val;
        }
        return ans;
    }
}

Java解法(队列)：

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public int[] levelOrder(TreeNode root) {
        ArrayList<Integer> list = new ArrayList<>();
        Queue<TreeNode> queue = new LinkedList<>();
        if(root == null)
        {
            return new int[0];
        }
        queue.add(root);
        list.add(root.val);
        while(queue.size() > 0)
        {
            TreeNode node = queue.remove();
            if(node.left != null)
            {
                queue.add(node.left);
                list.add(node.left.val);
            }
            if(node.right != null)
            {
                queue.add(node.right);
                list.add(node.right.val);
            }
        }
        int size = list.size();
        int[] ans = new int[size];
        for(int i = 0; i < size;i++)
        {
            ans[i] = list.get(i);
        }
        return ans;
    }
}

队列基本操作：

    add        增加一个元索             如果队列已满，则抛出一个IIIegaISlabEepeplian异常
　　remove   移除并返回队列头部的元素    如果队列为空，则抛出一个NoSuchElementException异常
　　element  返回队列头部的元素             如果队列为空，则抛出一个NoSuchElementException异常
　　offer       添加一个元素并返回true       如果队列已满，则返回false
　　poll         移除并返问队列头部的元素    如果队列为空，则返回null
　　peek       返回队列头部的元素             如果队列为空，则返回null
　　put         添加一个元素                      如果队列满，则阻塞
　　take        移除并返回队列头部的元素     如果队列为空，则阻塞

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/cong-shang-dao-xia-da-yin-er-cha-shu-lcof

最后编辑于：2020.04.21 14:04:33