剑指 Offer 32 - I. 从上到下打印二叉树

Love The Way You Lie 2022-09-09 04:53 132阅读 0赞

> 从上到下打印出二叉树的每个节点，同一层的节点按照从左到右的顺序打印。
> 
> 例如:  
> 给定二叉树: \[3,9,20,null,null,15,7\],
> 
> 3  
> / \\  
> 9 20  
> / \\  
> 15 7  
> 返回：
> 
> \[3,9,20,15,7\]  
> 
> 
> 提示：
> 
> 节点总数 <= 1000
> 
> 来源：力扣（LeetCode）  
> 链接：https://leetcode-cn.com/problems/cong-shang-dao-xia-da-yin-er-cha-shu-lcof  
> 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

此题目为二叉树的层次遍历。

不确定有多少层，也不确定每层多少个节点，所以使用队列+while循环来进行遍历。

一棵树：

3  
/ \\  
9 20  
/ \\  
15 7

若树不为空。

首先将 3 加入队列，

第一次while循环开始遍历，判断队列不为空。

3出队列，将 3 的子节点 9 , 20 依次加入队列，第一次while循环结束。

第二次while循环开始，判断队列不为空，

9出队，9 无子节点

第三次while循环开始，判断队列不为空，

20出队，加入20的左右子节点15,7

第四次while循环开始，判断队列不为空，

15出队，15无子节点

第五次while循环开始，判断队列不为空，

7出队，7无子节点，判断队列为空，结束循环。

遍历完毕。

class Solution {
        public int[] levelOrder(TreeNode root) {
            Queue<TreeNode> treeNodes = new LinkedList<>();
            ArrayList<Integer> arrayList = new ArrayList<>();
            TreeNode node;
            if(root == null)return new int[0];
            treeNodes.offer(root);
            while(!treeNodes.isEmpty()){
                node = treeNodes.poll();
                arrayList.add(node.val);
                if(node.left != null)treeNodes.offer(node.left);
                if(node.right != null)treeNodes.offer(node.right);
            }
            int[] levelNode = new int[arrayList.size()];
            int i = 0;
            for (Integer integer : arrayList) {
                levelNode[i++] = integer;
            }
            return levelNode;
    
        }
    }

向Queue中添加元素，异常较多的话，建议用offer方法

如果Queue中容量已满，add() 方法会抛出IllegalStateException异常，offer() 方法只会返回 false

remove()方法与poll()区别：

两者都是从队列中删除第一个元素。如果队列元素为空，调用remove() 会抛出异常，但是新的 poll() 方法在用空集合调用时只是返回 null。

element() 和 peek() 区别：

两者都是查询队列头部元素。在队列为空时， element() 抛出一个异常，而 peek() 返回 null。

--------------------

闭环思维。

闭环”的理论根据是由美国质量管理专家休哈特博士提出“PDCA循环”。

“PDCA 循环”将质量管理分为四个阶段：

P(Plan)计划：目标的确定和计划的制定。

D(Do)执行：具体运作，实现计划中的内容。