您当前位置：首页 > php开源 > php教程 > 按之字形顺序打印二叉树

按之字形顺序打印二叉树

来源：程序员人生发布时间：2016-07-05 14:34:02 阅读次数：2209次

题目

请实现1个函数依照之字形打印2叉树，即第1行依照从左到右的顺序打印，第2层依照从右至左的顺序打印，第3行依照从左到右的顺序打印，其他行以此类推。

解题

层次遍历2叉树很好理解
用队列临时寄存其中1层的结点，出队列更新到下1层结点
按之字形顺序打印2叉树需要两个栈。
在打印某1行结点时，把下1层的结点保存到相应的栈里。如果当前打印的是奇数层，则先保存左子结点再保存右子结点到第1个栈里；如果当前打印的是偶数层，则先保存右结点在保存左子结点到第2个栈里。

import java.util.ArrayList;
import java.util.*;
/*
public 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<Integer> row = new ArrayList<Integer>();
        ArrayList<ArrayList<Integer> > result = new  ArrayList<ArrayList<Integer> >();
        if(pRoot == null)
            return result;
        Stack<TreeNode> stack1 = new Stack<TreeNode>();
        Stack<TreeNode> stack2 = new Stack<TreeNode>();

        boolean flag = true;
        stack1.push(pRoot);
        while(!stack1.isEmpty() || !stack2.isEmpty()){
            row = new ArrayList<Integer>();
            if(flag){
                int size = stack1.size();
                while((size--) >0){
                    TreeNode node = stack1.pop();
                    row.add(node.val);
                    if(node.left!=null)
                        stack2.push(node.left);
                    if(node.right!=null)
                        stack2.push(node.right); 
                }
                flag = false;
            }else{
                int size = stack2.size();
                while((size--) >0){
                    TreeNode node = stack2.pop();
                    row.add(node.val);
                    if(node.right!=null)
                        stack1.push(node.right); 
                    if(node.left!=null)
                        stack1.push(node.left);

                }
                flag = true;
            }
            result.add(row);
        }
        return result;
    }

}

if else 程序写的很搓

用队列
层次遍历输出的每层元素都是左右的
对本题我们需要交叉的输出
左右输出
右左输出
所有只需要对偶数的行在层次遍历的基础上进行逆序就行了

import java.util.ArrayList;
import java.util.*;
/*
public 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<Integer> row = new ArrayList<Integer>();
         ArrayList<ArrayList<Integer> > result = new  ArrayList<ArrayList<Integer> >();
        if(pRoot == null)
            return result;
        boolean flag = true;
        Queue<TreeNode> queue = new LinkedList<TreeNode>();
        queue.offer(pRoot);
        while(!queue.isEmpty()){
            int size = queue.size();
            row = new ArrayList<Integer>();
            while((size--)>0){
                TreeNode node = queue.poll();
                row.add(node.val);
                if(node.left!=null)
                    queue.offer(node.left);
                if(node.right!=null)
                    queue.offer(node.right);
            }
            if(!flag){
                reverse(row);    
            }
            flag = !flag;
            result.add(row);


        }
        return result;
    }
    public void reverse(ArrayList<Integer> list){
        int i=0;
        int j=list.size() -1;
        while(i<j){
            swap(list,i,j);
            i++;
            j--;
        }
    }
    public void swap(ArrayList<Integer> list,int i,int j){
        int a = list.get(i);
        int b = list.get(j);
        list.set(i,b);
        list.set(j,a);
    }

}

生活不易，码农辛苦
如果您觉得本网站对您的学习有所帮助,可以手机扫描二维码进行捐赠
程序员人生

------分隔线----------------------------

上一篇 [置顶] Learning RNN from scratch (ＲＮＮ神经网络参数推导)

下一篇 [产品设计]华为云的产品经理不是一般得弱

分享到:

------分隔线----------------------------

为码而活

积分：4237

15粉丝

7关注

栏目热点