【剑指Offer】059——按之字形打印二叉树 （树、栈）

题目描述

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

解题思路

设两个栈，s2存放奇数层，s1存放偶数层
遍历s2节点的同时按照左子树、右子树的顺序加入s1，
遍历s1节点的同时按照右子树、左子树的顺序加入s2

参考代码

Java

import java.util.ArrayList;
import java.util.Stack;
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> > res = new ArrayList<ArrayList<Integer> >(); // 结果
        //利用两个栈的弹栈出栈，来模拟左右顺序
        Stack<TreeNode> s1 = new Stack<TreeNode>(); // 存放偶数层
        Stack<TreeNode> s2 = new Stack<TreeNode>(); // 存放奇数层
        int flag = 1;      // 利用标志位来控制顺序，为奇数，则从左到右的顺序，为偶数则相反
        if(pRoot == null)
            return res;
        s2.push(pRoot); // 奇数层添加
        ArrayList<Integer> temp = new ArrayList<Integer>(); // 临时
        //只要两个栈都不为空，则继续
        while(!s1.isEmpty() || !s2.isEmpty()){
            // 从左到右
            if(flag % 2 != 0){
                while(!s2.isEmpty()){
                    TreeNode node = s2.pop(); // 奇数存放的栈弹出
                    temp.add(node.val);  // 临时list添加数据
                    // 为偶数栈添加数据
                    if(node.left != null){
                        s1.push(node.left);
                    }
                    if(node.right != null){
                        s1.push(node.right);
                    }
                }
            }
            // 从右到左
            if(flag % 2 == 0){
                while(!s1.isEmpty()){
                    TreeNode node = s1.pop();
                    temp.add(node.val);
                    // 利用栈的特点从右往左添加
                    if(node.right != null){
                        s2.push(node.right);
                    }
                    if(node.left != null){
                        s2.push(node.left);
                    }
                }
            }
            res.add(new ArrayList<Integer>(temp));
            temp.clear();
            flag ++;
        }
        return res;
    }
}

Python

# -*- coding:utf-8 -*-
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
class Solution:
    def Print(self, pRoot):
        # write code here
        # 偶数层，奇数层，标记，结果，临时存储
        s1, s2, flag, res, temp = [], [], 1, [], []
        if not pRoot: return res
        s2.append(pRoot)
        while len(s1) > 0 or len(s2) > 0:
            if flag % 2 != 0:
                # 左->右
                while len(s2)>0:
                    node = s2.pop()
                    temp.append(node.val)
                    if node.left:
                        s1.append(node.left)
                    if node.right:
                        s1.append(node.right)
            if flag % 2 == 0:
                # 右->左
                while len(s1) >0:
                    node = s1.pop()
                    temp.append(node.val)
                    if node.right:
                        s2.append(node.right)
                    if node.left:
                        s2.append(node.left)
            res.append(temp)
            temp = []
            flag +=1
        return res

个人订阅号

image