剑指Offer（五十九）：按之字顺序打印二叉树

2018年1月29日10:48:25 6 4,348 °C
摘要

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

剑指Offer（五十九）：按之字顺序打印二叉树

一、前言

本系列文章为《剑指Offer》刷题笔记。

刷题平台：牛客网

书籍下载：共享资源

二、题目

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

1、思路

剑指Offer（五十九）：按之字顺序打印二叉树

按之字顺序打印上图二叉树，打印顺序为：

1

3 2

4 5 6 7

15 14 13 12 12 10 9 8

为了达到这样打印的效果，我们需要使用两个栈。我们在打印某一行结点时，把下一层的子结点保存到相应的栈里。如果当前打印的是奇数层（第一层、第三层等），则先保存左子树结点再保存右子树结点到第一个栈里。如果当前打印的是偶数层（第二层、第四层等），则则先保存右子树结点再保存左子树结点到第二个栈里。

剑指Offer（五十九）：按之字顺序打印二叉树

详细步骤，如上图所示。

2、代码

C++：

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
/*
struct TreeNode {
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
    TreeNode(int x) :
            val(x), left(NULL), right(NULL) {
    }
};
*/
class Solution {
public:
    vector<vector<int> > Print(TreeNode* pRoot) {
        vector<vector<int> > result;
        if(pRoot == NULL){
            return result;
        }
        stack<TreeNode* > s[2];
        s[0].push(pRoot);
        while(!s[0].empty() || !s[1].empty()){
            vector<int> v[2];
            // 偶数行
            while(!s[0].empty()){
                v[0].push_back(s[0].top()->val);
                if(s[0].top()->left != NULL){
                    s[1].push(s[0].top()->left);
                }
                if(s[0].top()->right != NULL){
                    s[1].push(s[0].top()->right);
                }
                s[0].pop();
            }
            if(!v[0].empty()){
                result.push_back(v[0]);
            }
            // 奇数行
            while(!s[1].empty()){
                v[1].push_back(s[1].top()->val);
                if(s[1].top()->right != NULL){
                    s[0].push(s[1].top()->right);
                }
                if(s[1].top()->left != NULL){
                    s[0].push(s[1].top()->left);
                }
                s[1].pop();
            }
            if(!v[1].empty()){
                result.push_back(v[1]);
            }
        }
        return result;
    }
};

Python：

感谢@小小毛提供python代码及本地测试用例。

Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
# -*- coding:utf-8 -*-
class TreeNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None
class Solution:
    """docstring for Solution"""      
    def Print(self, pRoot):
        resultArray = []
        if not pRoot:
            return resultArray
        curLayerNodes = [pRoot]
        isEvenLayer = True
        while curLayerNodes:
            curLayerValues = []
            nextLayerNodes = []
            isEvenLayer = not isEvenLayer
            for node in curLayerNodes:
                curLayerValues.append(node.val)
                if node.left:
                    nextLayerNodes.append(node.left)
                if node.right:
                    nextLayerNodes.append(node.right)
            curLayerNodes = nextLayerNodes
            resultArray.append(curLayerValues[::-1]) if isEvenLayer else resultArray.append(curLayerValues)
        return resultArray
 
if __name__ == '__main__':
    A1 = TreeNode(1)
    A2 = TreeNode(2)
    A3 = TreeNode(3)
    A4 = TreeNode(4)
    A5 = TreeNode(5)
    A6 = TreeNode(6)
    A7 = TreeNode(7)
 
    A1.left=A2
    A1.right=A3
    A2.left=A4
    A2.right=A5
    A3.left=A6
    A3.right=A7
 
    solution = Solution()
    ans=solution.Print(A1)
    print(ans)

weinxin
微信公众号
分享技术，乐享生活：微信公众号搜索「JackCui-AI」关注一个在互联网摸爬滚打的潜行者。
Jack Cui

发表评论

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen:

目前评论：6   其中：访客  4   博主  2

    • avatar 爱看的剧 来自天朝的朋友 谷歌浏览器 Mac OS X 10_12_6 上海市 上海理工大学 4
      回复 2018年7月19日 下午9:09  沙发

      第i层先入，则第i-1层节点先出，故用栈；层之间交替输出，故用两个栈。

      • avatar 爱看的剧 来自天朝的朋友 谷歌浏览器 Mac OS X 10_12_6 上海市 上海理工大学 4
        回复 2018年7月19日 下午10:15  板凳

        line25:不需要判断s[0].top()非空吗？即if(s[0].top() && s[0].top()->left != NULL)

          • avatar Jack Cui Admin 来自天朝的朋友 谷歌浏览器 Windows 10 北京市 百度网讯科技联通节点
            回复 2018年7月20日 上午9:29  1层

            @爱看的剧 while的时候已经判断了。

          • avatar 小小毛 来自天朝的朋友 谷歌浏览器 Windows 7 天津市 天津大学 3
            回复 2019年4月11日 下午5:25  地板

            1 按序获取每一层节点的值；
            2. 将偶数层节点的值倒序。
            # -*- coding:utf-8 -*-
            class TreeNode:
            def __init__(self, x):
            self.val = x
            self.left = None
            self.right = None
            class Solution:
            “””docstring for Solution”””
            def Print(self, pRoot):
            resultArray = []
            if not pRoot:
            return resultArray
            curLayerNodes = [pRoot]
            isEvenLayer = True
            while curLayerNodes:
            curLayerValues = []
            nextLayerNodes = []
            isEvenLayer = not isEvenLayer
            for node in curLayerNodes:
            curLayerValues.append(node.val)
            if node.left:
            nextLayerNodes.append(node.left)
            if node.right:
            nextLayerNodes.append(node.right)
            curLayerNodes = nextLayerNodes
            resultArray.append(curLayerValues[::-1]) if isEvenLayer else resultArray.append(curLayerValues)
            return resultArray

            if __name__ == ‘__main__’:
            A1 = TreeNode(1)
            A2 = TreeNode(2)
            A3 = TreeNode(3)
            A4 = TreeNode(4)
            A5 = TreeNode(5)
            A6 = TreeNode(6)
            A7 = TreeNode(7)

            A1.left=A2
            A1.right=A3
            A2.left=A4
            A2.right=A5
            A3.left=A6
            A3.right=A7

            solution = Solution()
            ans=solution.Print(A1)
            print(ans)

              • avatar Jack Cui Admin 来自天朝的朋友 Safari浏览器 Mac OS X 10_14_3 北京市 百度网讯科技联通节点
                回复 2019年4月11日 下午5:27  1层

                @小小毛 优秀～！

              • avatar feng 来自天朝的朋友 谷歌浏览器 Windows 10 黑龙江省哈尔滨市 哈尔滨工业大学 0
                回复 2019年12月24日 下午4:01  4楼

                赞！