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

解題思路

這道題可以借助兩個棧來實現(xiàn),，用文字不好描述,，也許直接看代碼會好一些

import java.util.ArrayList;
import java.util.Stack;
public class Solution {
    public ArrayList<ArrayList<Integer> > Print(TreeNode pRoot) {
    	// 用來存放結(jié)點
        ArrayList<ArrayList<Integer>> list = new ArrayList<>();
        if(pRoot == null) {
            return list; 
        }
        // 判斷奇偶層
        int layer = 1;
        // 存放奇數(shù)層結(jié)點
        Stack<TreeNode> s1 = new Stack<>();
        // 存放偶數(shù)層結(jié)點
        Stack<TreeNode> s2 = new Stack<>();
        // 先把根結(jié)點放入奇數(shù)層
        s1.push(pRoot);
        // 如果兩個棧都為空，那么就證明所有結(jié)點都已遍歷完畢
        while(!s1.empty() || !s2.empty()) {
        	// 當(dāng)前層是奇數(shù)層
            if(layer % 2 != 0) {
            	// 存放奇數(shù)層的結(jié)點
                ArrayList<Integer> temp = new ArrayList<>();
                // 把奇數(shù)層的結(jié)點逐個彈出,，用 temp 保存起來
                // 同時把每個彈出結(jié)點的左右子結(jié)點壓入棧
                // 要注意棧的特點是后進(jìn)先出,，因此出棧順序和入棧順序是相反的
                while(!s1.empty()) {
                    TreeNode node = s1.pop();
                    if(node != null) {
                        temp.add(node.val);
                        s2.push(node.left);
                        s2.push(node.right);
                    }
                }
                if(!temp.isEmpty()) {
                    list.add(temp);
                    layer++;
                }
            } else {
            	// 原理同上
                ArrayList<Integer> temp = new ArrayList<>();
                while(!s2.empty()) {
                    TreeNode node = s2.pop();
                    if(node != null) {
                        temp.add(node.val);
                        s1.push(node.right);
                        s1.push(node.left);
                    }
                }
                if(!temp.isEmpty()) {
                    list.add(temp);
                    layer++;
                }
            }
        }
        return list;
    }
}