《剑指offer》按之字顺序打印二叉树-ag真人游戏

题目描述：

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

解题思路：

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

1

3 2

4 5 6 7

15 14 13 12 12 10 9 8

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

详细步骤，如上图所示。

代码实现(c )

/*
struct treenode {
    int val;
    struct treenode *left;
    struct treenode *right;
    treenode(int x) :
            val(x), left(null), right(null) {
    }
};
*/
class solution {
public:
    vector > print(treenode* proot) {
        vector > result;
        if(proot == null){
            return result;
        }
        stack s[2];
        s[0].push(proot);
        while(!s[0].empty() || !s[1].empty()){
            vector 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)

# -*- 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)