快捷導航

詳解java實現(xiàn)遍歷二叉樹的三種情況

更新時間：2017年04月27日 09:57:30 作者：linkinparkzlz

這篇文章主要介紹了java實現(xiàn)遍歷二叉樹的三種情況,小編覺得挺不錯的，現(xiàn)在分享給大家，也給大家做個參考。一起跟隨小編過來看看吧

遍歷二叉樹，從上往下遍歷。但是同層節(jié)點可以從左向右遍歷，也可以從右向左遍歷（也就是之字型遍歷），其中，都需要隊列進行實現(xiàn)。只是按照之字型稍微麻煩一些。

（1）從上往下打印出二叉樹的每個節(jié)點，同層節(jié)點從左至右打印。

需要一個隊列，隊列里面放節(jié)點（從根節(jié)點開始），然后依次進行打印。

import java.util.ArrayList;
import java.util.Queue;
import java.util.LinkedList;
class TreeNode{
 int val = 0;
 TreeNode left = null;
 TreeNode right = null;

 public TreeNode(int val){
  this.val = val;
 }
}

public class Solution {
  public ArrayList<Integer> PrintFromTopToBottom(TreeNode root) {
   ArrayList<Integer> list = new ArrayList<Integer>();
   if(root == null) 
    return list;
   Queue<TreeNode> queue = new LinkedList<TreeNode>();

   queue.add(root);
   while(!queue.isEmpty()){
    TreeNode t = queue.poll();
    list.add(t.val);
    if(t.left != null) queue.add(t.left);
    if(t.right != null) queue.add(t.right);
   }
   return list;
  }
}

（2）請實現(xiàn)一個函數(shù)按照之字形打印二叉樹，即第一行按照從左到右的順序打印，第二層按照從右至左的順序打印，第三行按照從左到右的順序打印，其他行以此類推。

解析：之字形打印二叉樹，不要將所有層放入ArrayList中后再將偶數(shù)層進行reverse()，這樣可以實現(xiàn)，但是數(shù)據(jù)量大的時候效率太低。

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
 class TreeNode {
 int val = 0;
 TreeNode left = null;
 TreeNode right = null;

 public TreeNode(int val) {
  this.val = val;

 }

}

public class Solution {
 public ArrayList<ArrayList<Integer> > Print(TreeNode pRoot) {
  ArrayList<ArrayList<Integer>> result=new ArrayList<ArrayList<Integer>>();
  if(pRoot==null){
   return result;
  }

  Queue<TreeNode> queue = new LinkedList<TreeNode>();
  int rows=1;
  queue.add(pRoot);
  while(!queue.isEmpty()){
   ArrayList<Integer> list=new ArrayList();
   int size=queue.size();
   for(int i=0;i<size;i++){
    TreeNode t=queue.poll();
    if(rows%2==0){
     list.add(0,t.val); //將元素插入指定位置（頭部），也就相當于倒序了
    }else{
     list.add(t.val); //將元素插入尾部
    }
    if(t.left!=null){
     queue.offer(t.left);
    }
    if(t.right!=null){
     queue.offer(t.right);
    }
   }
   result.add(list);
   rows++;
  }
  return result;

 }

}

（3）從上到下按層打印二叉樹，同一層結(jié)點從左至右輸出。每一層輸出一行。

這道題就是典型的二叉樹層次遍歷。

思路：因為我們要按層打印，所以需要設(shè)置標志量。

其次：我們需要三個集合：

第一個集合用于存放結(jié)果集

第二個集合用于臨時存放每一層的結(jié)果，等到一層結(jié)束之后，再將其加入到最終結(jié)果集中。注意，每一次使用完這個集合之后，需要將其清空，以便下一次存放。

第三個集合用于存放節(jié)點。

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.*;

class TreeNode
{
 int val = 0;
 TreeNode left = null;
 TreeNode right = null;

 public TreeNode(int val)
 {
  this.val = val;

 }

}

public class Solution
{
 ArrayList<ArrayList<Integer>> Print(TreeNode pRoot)
 {

  ArrayList<ArrayList<Integer>> result = new ArrayList<ArrayList<Integer>>();

  ArrayList<Integer> arrayList = new ArrayList<Integer>();

  Queue<TreeNode> queue = new LinkedList<TreeNode>(); // 存放節(jié)點

  // 檢查是否為空
  if (pRoot == null)
   return result;

  queue.add(pRoot);

  int start = 0;
  int end = 1; // 第一行

  while (!queue.isEmpty())
  {
   TreeNode treeNode = queue.poll();
   end--;
   arrayList.add(treeNode.val);

   if (treeNode.left != null) // 如果有左節(jié)點
   {
    queue.add(treeNode.left);// 將左節(jié)點加入linkedList中
    start++; // 標志進入下一行
   }
   if (treeNode.right != null)
   {
    queue.add(treeNode.right);
    start++; // 標志進入下一行
   }

   if (end == 0)
   { // 此時也就是說明把一層已經(jīng)打印完了，應(yīng)該將其加入結(jié)果集中
    result.add(new ArrayList<Integer>(arrayList)); // 加入結(jié)果集中
    arrayList.clear();// 必須將臨時存放結(jié)果的集合清空，以便進行下一次存放
    end = start; // 恢復原狀
    start = 0;

   }

  }

  return result;

 }

}

以上就是本文的全部內(nèi)容，希望對大家的學習有所幫助，也希望大家多多支持腳本之家。

您可能感興趣的文章: