• 劍指 Offer 面試題 60（Java 版）：把二叉樹(shù)打印成多行

題目：從上到下按層打印二叉樹(shù)，同一層的結(jié)點(diǎn)按從左到右的順序打印，每一層打印一行。

思路：用一個(gè)隊(duì)列來(lái)保存將要打印的結(jié)點(diǎn)。為了把二叉樹(shù)的每一行單獨(dú)打印到一行里，我們需要兩個(gè)變量：一個(gè)變量表示在當(dāng)前的層中還沒(méi)有打印的結(jié)點(diǎn)數(shù)，另一個(gè)變量表示下一次結(jié)點(diǎn)的數(shù)目。

show my code

/**
 * 按行打印二叉樹(shù)
 * @author innovator
 *
 */
public class PrintTree {

    /**
     * 按照層來(lái)打印二叉樹(shù)
     * @param root
     */
    public static void printTreeByLine(BinaryTreeNode root){
        
        if(root == null){
            return;
        }
        
        //用隊(duì)列來(lái)裝遍歷到的節(jié)點(diǎn)
        Queue<BinaryTreeNode> queue = new LinkedList<>();
        
        queue.add(root);
        //下一層節(jié)點(diǎn)數(shù)目
        int nextLevel = 0;
        //當(dāng)前層中未被打印的節(jié)點(diǎn)數(shù)
        int toBePrinted = 1;
        
        while(!queue.isEmpty()){
            
            BinaryTreeNode current = queue.peek();
            //打印當(dāng)前節(jié)點(diǎn)
            System.out.printf(" %d",current.value);
            
            //層序遍歷
            if(current.leftNode != null){
                queue.add(current.leftNode);
                nextLevel ++;
            }
            
            if(current.rightNode != null){
                queue.add(current.rightNode);
                nextLevel ++;
            }
            
            //彈出當(dāng)前節(jié)點(diǎn)，出隊(duì)
            queue.poll();
            toBePrinted --;
            
            //當(dāng)前層已經(jīng)打印完畢
            if(toBePrinted == 0){
                //輸出換行
                System.out.printf("\n");
                //從下層開(kāi)始打印
                toBePrinted = nextLevel;
                nextLevel = 0;
            }
        }
    }
    
    
//                     8
//           6                    10
//      5         7          9          11
    public static void main(String[] args){
        BinaryTreeNode root =  new BinaryTreeNode(8);
        BinaryTreeNode node1 = new BinaryTreeNode(6);
        BinaryTreeNode node2 = new BinaryTreeNode(10);
        BinaryTreeNode node3 = new BinaryTreeNode(5);
        BinaryTreeNode node4 = new BinaryTreeNode(7);
        BinaryTreeNode node5 = new BinaryTreeNode(9);
        BinaryTreeNode node6 = new BinaryTreeNode(11);
        
        root.leftNode = node1;
        root.rightNode = node2;
        node1.leftNode = node3;
        node1.rightNode = node4;
        node2.leftNode = node5;
        node2.rightNode = node6;
    
        printTreeByLine(root);
    }
}

結(jié)果

• 劍指 Offer 面試題 61（Java 版）：按之字形順序打印二叉樹(shù)

題目：請(qǐng)實(shí)現(xiàn)一個(gè)函數(shù)按照之字形順序打印二叉樹(shù)，即第一行按照從左到右的順序打印，第二層按照從右到左的順序打印，即第一行按照從左到右的順序打印，第二層按照從右到左順序打印，第三行再按照從左到右的順序打印，其他以此類(lèi)推。

思路：按之字形順序打印二叉樹(shù)需要兩個(gè)棧。我們?cè)诖蛴∧骋恍薪Y(jié)點(diǎn)時(shí)，把下一層的子結(jié)點(diǎn)保存到相應(yīng)的棧里。如果當(dāng)前打印的是奇數(shù)層，則先保存左子結(jié)點(diǎn)再保存右子結(jié)點(diǎn)到一個(gè)棧里；如果當(dāng)前打印的是偶數(shù)層，則先保存右子結(jié)點(diǎn)再保存左子結(jié)點(diǎn)到第二個(gè)棧里。

show my code

/**
 * 按照之字順序打印二叉樹(shù)
 * @author innovator
 *
 */
public class PrintTreeByZHI {

    /**
     * 按照之字順序打印二叉樹(shù)
     * @param root
     */
    public static void printTree(BinaryTreeNode root){
        
        if(root == null){
            return;
        }
        
        //存放奇數(shù)層的結(jié)點(diǎn)
        Stack<BinaryTreeNode> stack1 = new Stack<>();
        //存放偶數(shù)層的結(jié)點(diǎn)
        Stack<BinaryTreeNode> stack2 = new Stack<>();
        
        //是否在打印奇數(shù)層
        int printFlag = 1;
        
        BinaryTreeNode current;
        
        stack1.push(root);
        //還有結(jié)點(diǎn)在棧中未打印
        while(!stack1.isEmpty() || !stack2.isEmpty()){
            
            if(printFlag == 1){
                current = stack1.pop();
            }else{
                current = stack2.pop();
            }
            
            System.out.printf(" "+ current.value);
            
            //將下一層的結(jié)點(diǎn)入棧
            if(printFlag == 1){
                //壓入偶數(shù)棧
                //先左后右
                if(current.leftNode != null){
                    stack2.push(current.leftNode);
                }
                
                if(current.rightNode != null){
                    stack2.push(current.rightNode);
                }
            }else{
                //壓入奇數(shù)棧
                //先右后左
                if(current.rightNode != null){
                    stack1.push(current.rightNode);
                }
                
                if(current.leftNode != null){
                    stack1.push(current.leftNode);
                }
                
            }
            
            
            //打印完了奇數(shù)層，輪到偶數(shù)層了
            //加了前面的判斷是為了防止當(dāng)下一行為空的時(shí)候，會(huì)跑進(jìn)去打印換行，打印完了當(dāng)前的棧才允許切換flag
            if(printFlag == 1 && stack1.isEmpty()){
                System.out.printf("\n");
                printFlag = 0;
            }
            
            //打印完了偶數(shù)層，輪到奇數(shù)層了
            if(printFlag == 0 && stack2.isEmpty()){
                System.out.printf("\n");
                printFlag = 1;
            }
        }
    }
    
//                  8
//          6                    10
//      5         7          9          11
    public static void main(String[] args){
        BinaryTreeNode root =  new BinaryTreeNode(8);
        BinaryTreeNode node1 = new BinaryTreeNode(6);
        BinaryTreeNode node2 = new BinaryTreeNode(10);
        BinaryTreeNode node3 = new BinaryTreeNode(5);
        BinaryTreeNode node4 = new BinaryTreeNode(7);
        BinaryTreeNode node5 = new BinaryTreeNode(9);
        BinaryTreeNode node6 = new BinaryTreeNode(11);
        
        root.leftNode = node1;
        root.rightNode = node2;
        node1.leftNode = node3;
        node1.rightNode = node4;
        node2.leftNode = node5;
        node2.rightNode = node6;
    
        printTree(root);
    }
}

結(jié)果