劍指Offer系列(java版,詳細解析)32.從上到下打印二叉樹

程序員社區 2022-01-08 03:23:22 阅读数:112

offer 系列 java 解析 上到

題目描述

劍指 Offer 32 - I. 從上到下打印二叉樹

難度中等72

從上到下打印出二叉樹的每個節點,同一層的節點按照從左到右的順序打印。

例如:
給定二叉樹: [3,9,20,null,null,15,7],

 3 / \ 9 20 / \ 15 7

返回:

[3,9,20,15,7]

二叉樹節點如下:

public class BinaryTreeNode {
 int value; BinaryTreeNode left; BinaryTreeNode right;}

測試用例

  • 功能測試(完全二叉樹;所有節點只有左子樹的二叉樹;所有節點只有右子樹的二叉樹)
  • 特殊功能測試(二叉樹根節點為空指針;只有一個節點的二叉樹)

題目考點

  • 考察應聘者的思維能力,想到用隊列處理按層遍曆。
  • 考察應聘者對二叉樹及隊列的理解。

解題思路

這道題如果能想到隊列,編碼還是很簡單的。不逼逼了!!!

  1. 先將頭節點放入隊列
  2. 當隊列不為空的時候,從隊列取出一個節點輸出
  3. 判斷取出的節點左右節點是否為空,不為空則將他們加入隊列
  4. 循環至隊列為空跳出

參考解題

class Solution {
 public int[] levelOrder(TreeNode root) {
 if(root==null) return new int[0]; Queue<TreeNode> queue = new LinkedList<>(){
{
 add(root); }}; ArrayList<Integer> ans = new ArrayList<>(); while(!queue.isEmpty()){
 TreeNode tmp = queue.poll(); ans.add(tmp.val); if(tmp.left!=null) queue.add(tmp.left); if(tmp.right!=null) queue.add(tmp.right); } int[] res = new int[ans.size()]; for(int i = 0; i < ans.size(); i++) res[i] = ans.get(i); return res; }}

劍指 Offer 32 - II. 從上到下打印二叉樹 II

難度簡單93

從上到下按層打印二叉樹,同一層的節點按從左到右的順序打印,每一層打印到一行。

例如:
給定二叉樹: [3,9,20,null,null,15,7],

 3 / \ 9 20 / \ 15 7

返回其層次遍曆結果:

[ [3], [9,20], [15,7]]
/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */class Solution {
 public List<List<Integer>> levelOrder(TreeNode root) {
 List<List<Integer>> res = new ArrayList(); Queue<TreeNode> queue = new LinkedList(); if(root != null) queue.add(root); while(!queue.isEmpty()){
 List<Integer> list = new ArrayList(); int len = queue.size(); for(int i=0;i<len;i++){
 TreeNode tmp = queue.poll(); list.add(tmp.val); if(tmp.left!=null) queue.add(tmp.left); if(tmp.right!=null) queue.add(tmp.right); } res.add(list); } return res; }}

劍指 Offer 32 - III. 從上到下打印二叉樹 III

難度中等86

請實現一個函數按照之字形順序打印二叉樹,即第一行按照從左到右的順序打印,第二層按照從右到左的順序打印,第三行再按照從左到右的順序打印,其他行以此類推。

例如:
給定二叉樹: [3,9,20,null,null,15,7],

 3 / \ 9 20 / \ 15 7

返回其層次遍曆結果:

[ [3], [20,9], [15,7]]

提示:

  1. 節點總數 <= 1000
class Solution { public List<List<Integer>> levelOrder(TreeNode root) { Queue<TreeNode> queue = new LinkedList<>(); List<List<Integer>> res = new ArrayList<>(); if(root != null) queue.add(root); while(!queue.isEmpty()) { LinkedList<Integer> tmp = new LinkedList<>(); for(int i = queue.size(); i > 0; i--) { TreeNode node = queue.poll(); if(res.size() % 2 == 0) tmp.addLast(node.val); // 偶數層 -> 隊列頭部 else tmp.addFirst(node.val); // 奇數層 -> 隊列尾部 if(node.left != null) queue.add(node.left); if(node.right != null) queue.add(node.right); } res.add(tmp); } return res; }}
版权声明:本文为[程序員社區]所创,转载请带上原文链接,感谢。 https://gsmany.com/2022/01/202201080323217460.html