题解 | #按之字形顺序打印二叉树#

1. 参照使用两个栈的方法
2. 为啥要用栈，而不用队列。其实因为使用栈，就正常的入栈出栈就行，而正常的FIFO队列，不行（需要额外的操作）
3. 栈这种先进后出的特性，正好可以方便实现反过来打印下一层

/**
 * #[derive(PartialEq, Eq, Debug, Clone)]
 * pub struct TreeNode {
 *     pub val: i32,
 *     pub left: Option<Box<TreeNode>>,
 *     pub right: Option<Box<TreeNode>>,
 * }
 *
 * impl TreeNode {
 *     #[inline]
 *     fn new(val: i32) -> Self {
 *         TreeNode {
 *             val: val,
 *             left: None,
 *             right: None,
 *         }
 *     }
 * }
 */
struct Solution {}

impl Solution {
    fn new() -> Self {
        Solution {}
    }

    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param pRoot TreeNode类
     * @return int整型二维数组
     */
    pub fn Print(&self, pRoot: Option<Box<TreeNode>>) -> Vec<Vec<i32>> {
        // write code here
        // 奇数从左到右打印，偶数从右到左打印
        let mut level = 1;
        // let mut ret: Vec<Vec<i32>> = vec![Vec::new()];
        let mut ret = vec![];
        let mut s1 = vec![];
        let mut s2 = vec![];

        if pRoot.is_none() {
            return ret;
        }

        let mut pRoot = pRoot.unwrap();
        s1.push(Some(pRoot));

        while s1.len() > 0 || s2.len() > 0 {
            //从左到右打印
            if level % 2 == 1 {
                let mut t_vec = vec![];
                while s1.len() > 0 {
                    if let Some(Some(tmp)) = s1.pop() {
                        t_vec.push(tmp.val);
                        s2.push(tmp.left);
                        s2.push(tmp.right);
                    }
                }
                level += 1;
                if t_vec.len() > 0 {
                    ret.push(t_vec);
                }
            }
            //从右到左打印
            else {
                let mut t_vec = vec![];
                while s2.len() > 0 {
                    if let Some(Some(tmp)) = s2.pop() {
                        t_vec.push(tmp.val);
                        s1.push(tmp.right);
                        s1.push(tmp.left);
                    }
                }
                level += 1;
                if t_vec.len() > 0 {
                    ret.push(t_vec);
                }
            }
        }
        ret
    }
}