102. Binary Tree Level Order Traversal

发布时间：2020-12-14 04:21:45 所属栏目：大数据来源：网络整理

导读：一、题目 1、审题 2、分析给出一个二叉树，将每一层节点值放在一个集合中，最终返回每一层节点值的所有集合。 ? 二、解答 1、思路：方法一、 ①、首先，二叉树父即节点入队列。 ②、队列头结点依次出队列，直到队列为空，并将每次出队列的队头节点放在一个

一、题目

　　1、审题

　　2、分析

　　给出一个二叉树，将每一层节点值放在一个集合中，最终返回每一层节点值的所有集合。

二、解答

　　1、思路：

　　　　方法一、

　　　　①、首先，二叉树父即节点入队列。

　　　　②、队列头结点依次出队列，直到队列为空，并将每次出队列的队头节点放在一个?List?中

　　　　③、若队列为空时，说明这一层所有节点都放入了?List?中，此时，将?List?中节点的非空子节点依次入队列，即为下一层的所有节点；

　　　　　　?同时将此时?List?中的所有节点值放在一个集合中记录，并清空?List，?开始下一层节点的遍历。

　　　　④、若?队列与?List?均为空，说明查找结束。

    public List<List<Integer>> levelOrder(TreeNode root) {
        
        List<List<Integer>> resultList = new ArrayList<List<Integer>>();
        
        if(root == null) 
            return resultList;
        
        Queue<TreeNode> queue = new LinkedList<TreeNode>();
        queue.add(root);
        List<TreeNode> list = new LinkedList<TreeNode>();
        while(!queue.isEmpty()) {
            list.add(queue.poll());    // 队列头结点入 List
            
            if(queue.isEmpty() && list.size() > 0) {
                
                List<Integer> targetList = new LinkedList<Integer>();
                for(TreeNode tmpNode: list) {
                    targetList.add(tmpNode.val);
                    if(tmpNode.left != null)
                        queue.add(tmpNode.left);
                    if(tmpNode.right != null)
                        queue.add(tmpNode.right);
                }
                list.clear();
                resultList.add(targetList);
            }
        }
        
        return resultList;
    }

　　方法二、

　　　　直接利用?queue.size()?属性，获取队列中这一层元素的个数。

    public List<List<Integer>> levelOrder2(TreeNode root) {
        
        List<List<Integer>> resultList = new ArrayList<List<Integer>>();
        
        if(root == null) 
            return resultList;
        
        Queue<TreeNode> queue = new LinkedList<TreeNode>();
        queue.add(root);
        while (!queue.isEmpty()) {
            int levelNum = queue.size();
            List<Integer> subList = new LinkedList<>();
            for(int i = 0; i < levelNum; i++) {
                TreeNode node = queue.poll();
                if(node.left != null)
                    queue.add(node.left);
                if(node.right != null)
                    queue.add(node.right);
                subList.add(node.val);
            }
            resultList.add(subList);
        }
        return resultList;
    }

　　方法三、

　　　　采用递归将每一层的节点放入一个?List?中。

    public List<List<Integer>> levelOrder(TreeNode root) {
        
        List<List<Integer>> resultList = new ArrayList<List<Integer>>();
        levelHelper(resultList,root,0);
        return resultList;
    }
    
    private void levelHelper(List<List<Integer>> resultList,TreeNode root,int height) {
        
        if(root == null) return;
        
        if(height >= resultList.size())
            resultList.add(new LinkedList<Integer>());
        
        resultList.get(height).add(root.val);
        levelHelper(resultList,root.left,height+1);
        levelHelper(resultList,root.right,height+1);
    }

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!