103. 二叉树的锯齿形层次遍历

题意：

解题思路：

思路：
递归(dfs)：O(n)
1. 递归一层记录一层数据，每层level+1，记录层级；
2. 每层判断奇偶性，奇数的话按照逆序插入，偶数的话按照先后顺序插入

PHP代码实现：

/**
 * Definition for a binary tree node.
 * class TreeNode {
 *     public $val = null;
 *     public $left = null;
 *     public $right = null;
 *     function __construct($value) { $this->val = $value; }
 * }
 */
class Solution {
    /**
     * @param TreeNode $root
     * @return Integer[][]
     */
    function zigzagLevelOrder($root) {
        $res = [];
        if (!$root) return $res;
        $this->dfs($root, 0, $res);
        return $res;
        $queue = [];
        array_push($queue, $root);
        $level = 0;
        while (!empty($queue)) {
            $list = [];
            foreach ($queue as $r) {
                if ($level % 2 == 0) {
                    array_push($list, $r->val);
                } else {
                    array_unshift($list, $r->val);
                }
                if ($r->left != null) array_push($queue, $r->left);
                if ($r->right != null) array_push($queue, $r->right);
                array_shift($queue);
            }
            array_push($res, $list);
            $level++;
        }
        return $res;
    }
    function dfs($root, $level, &$res) {
        if (!$root) return $res;
        if ($level == count($res)) {
            $res[$level] = [];
        }
        if ($level % 2 == 0) {
            array_push($res[$level], $root->val);
        } else {
            array_unshift($res[$level], $root->val);
        }
        $this->dfs($root->left, $level + 1, $res);
        $this->dfs($root->right, $level + 1, $res);
    }
}

GO代码实现：

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func zigzagLevelOrder(root *TreeNode) [][]int {
    return zigzagLevelOrders(root);
    if root == nil {
        return nil
    }
    queue := []*TreeNode{root}
    var res [][]int
    index := 0
    for {
        lq := len(queue)
        if lq == 0 {
            break
        }
        res = append(res, make([]int, lq)) // 申请存储空间
        for i := 0; i < lq; i++ {
            node := queue[0]
            queue = queue[1:]
            if index&1 == 0 { // 偶数从左往右
                res[index][i] = node.Val
            } else { // 奇数从右往左
                res[index][lq-i-1] = node.Val
            }
            if node.Left != nil {
                queue = append(queue, node.Left)
            }
            if node.Right != nil {
                queue = append(queue, node.Right)
            }
        }
        index++
    }
    return res
}
func zigzagLevelOrders(root *TreeNode) [][]int {
    var res = [][]int{}
    dfs(root, 0, &res)
    return res
}
func dfs(root *TreeNode, level int, res *[][]int) {
    if root == nil {
        return
    }
    if level == len(*res) {
        *res = append(*res, []int{})
    }
    // 偶数压缩到末尾
    if level % 2 == 0 {
        (*res)[level] = append((*res)[level], root.Val)
    } else {
        (*res)[level] = append([]int{root.Val}, (*res)[level]...)
    }
    dfs(root.Left, level+1, res)
    dfs(root.Right, level+1, res)
}