二叉树的锯齿形层序遍历(每日一题)

leetcode 笔记

题目描述：

给定一个二叉树，返回其节点值的锯齿形层序遍历。（即先从左往右，再从右往左进行下一层遍历，以此类推，层与层之间交替进行）。

例如：给定二叉树 [3,9,20,null,null,15,7],

返回锯齿形层序遍历如下：

[
  [3],
  [20,9],
  [15,7]
]

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/binary-tree-zigzag-level-order-traversal
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

code

二叉树的层次遍历。

至于从前往后还是从后往前读，无非是个下标的问题。开一个和当前层等长的数组，如果从后往前读则下标倒序，把当前层的val插入到数组里。

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    vector<vector<int>> zigzagLevelOrder(TreeNode* root) {
        if(root == nullptr) return {};

        vector<vector<int>> ans;

        queue<TreeNode *> q;
        q.push(root);
        bool reverse = false;
        while(!q.empty()) {
            int len = q.size();
            vector<int> tmp(len, 0);
            for(int i = 0; i < len; i++) {
                root = q.front();
                q.pop();
                tmp[reverse ? len - i - 1 : i] = root -> val;
                if(root -> left != nullptr) q.push(root -> left);
                if(root -> right != nullptr) q.push(root -> right);
            }
            ans.push_back(move(tmp));
            reverse = !reverse;
        }
        return ans;
    }
};

函数式语言里, 利用flatMap可以很容易的拿到下一层节点组成的集合, map得到当前层节点val的集合。

kotlin

尾递归函数 tailrec fun zigzagLevelOrder:

ans: List<List<Int>> : 当前的累计结果

list: List<TreeNode> : 当前层节点。

reverse: Boolean : 是否要倒序

如果当前层没有节点, 说明到底了, 返回ans; 否则， ans + 当前层节点val的集合作为新的累计结果， list.flatMap{ it -> listOfNotNull(it.left, it.right) } 得到下一层非空节点的集合，开始调用下一层

所以可以一行，一刀流。

tailrec fun zigzagLevelOrder(ans: List<List<Int>>, list: List<TreeNode>, reverse: Boolean): List<List<Int>> = if (list.isEmpty()) ans else zigzagLevelOrder(ans + listOf(list.map { it.`val` }.let { if (reverse) it.asReversed() else it }), list.flatMap { listOfNotNull(it.left, it.right) }, !reverse)

class Solution {
    fun zigzagLevelOrder(root: TreeNode?): List<List<Int>> {
        root ?: return emptyList()

        tailrec fun zigzagLevelOrder(ans: List<List<Int>>, list: List<TreeNode>, reverse: Boolean): List<List<Int>> =
            if (list.isEmpty()) ans
            else
                zigzagLevelOrder(
                    ans + listOf(list.map { it.`val` }.let { if (reverse) it.asReversed() else it }),
                    list.flatMap { listOfNotNull(it.left, it.right) },
                    !reverse
                )


        return zigzagLevelOrder(emptyList(), listOf(root), false)
    }
}

scala

一刀流

@tailrec
def zigzagLevelOrder(ans: List[List[Int]], list: List[TreeNode], reverse: Boolean): List[List[Int]] = if (list.isEmpty) ans else zigzagLevelOrder(ans ::: List(if (reverse) list.map(_.value).reverse else list.map(_.value)) ::: Nil, list flatMap (it => it.left :: it.right :: Nil) filter (_ != null), !reverse)

/**
 * Definition for a binary tree node.
 * class TreeNode(var _value: Int) {
 *   var value: Int = _value
 *   var left: TreeNode = null
 *   var right: TreeNode = null
 * }
 */

import scala.annotation.tailrec

object Solution {

  def zigzagLevelOrder(root: TreeNode): List[List[Int]] = {
    if (root == null) return Nil

    @tailrec
    def zigzagLevelOrder(ans: List[List[Int]], list: List[TreeNode], reverse: Boolean): List[List[Int]] =
      if (list.isEmpty) ans
      else
        zigzagLevelOrder(
          ans ::: List(if (reverse) list.map(_.value).reverse else list.map(_.value)) ::: Nil,
          list flatMap (it => it.left :: it.right :: Nil) filter (_ != null),
          !reverse
        )


    zigzagLevelOrder(Nil, List(root), reverse = false)
  }
}

rust

这种数据结构题用 Rust 很不地道。尤其是一刀流，会比普通写法还长，函数栈的原因要多耗点内存。算法复杂度相同的话，两种写法耗时不会有差距

// 一刀流 花括号不能省，导致很长
impl Solution {
    pub fn zigzag_level_order(root: Option<Rc<RefCell<TreeNode>>>) -> Vec<Vec<i32>> {
        if let Some(i) = root {
            fn zigzag_level_order(
                mut ans: Vec<Vec<i32>>,
                cur: Vec<Rc<RefCell<TreeNode>>>,
                reverse: bool,
            ) -> Vec<Vec<i32>> {
                if cur.is_empty() {
                    ans
                } else {
                    zigzag_level_order(
                        {
                            let tmp = cur.iter().map(|i| i.borrow().val);
                            ans.push(if reverse {
                                tmp.rev().collect()
                            } else {
                                tmp.collect()
                            });
                            ans
                        },
                        cur.iter().fold(vec![], |mut acc, i| {
                            if let Some(ref left) = i.borrow().left {
                                acc.push(left.clone())
                            }
                            if let Some(ref right) = i.borrow().right {
                                acc.push(right.clone())
                            }
                            acc
                        }),
                        !reverse,
                    )
                }
            }
            zigzag_level_order(vec![], vec![i], false)
        } else {
            vec![]
        }
    }
}

I'm Prime

十方三世，尽在一念

leetcode 笔记

题目描述：

code

c++

kotlin

scala