Lzyprime blog (Github) was created on December 22, 2020.qq and email: 2383518170

Leetcode notes

Title description:

Given a binary tree, return a zigzag sequence traversal of its node values. (that is, the next layer is traversed from left to right, then right to left, and so on, alternating between layers).

For example, given a binary tree [3,9,20,null,null,15,7],

    3
   / \
  9  20
    /  \
   15   7
Copy the code

Return the zigzag sequence traversal as follows:

[[3], [20,9], [15,7]Copy the code

Source: LeetCode link: leetcode-cn.com/problems/bi… Copyright belongs to the Collar buckle network. Commercial reprint please contact official authorization, non-commercial reprint please indicate the source.

code

Hierarchical traversal of a binary tree.

As for whether to read from back to front or from back to front, it is nothing but a matter of subscript. Open an array as long as the current layer, and insert the current layer’s val into the array if you read from back to front.

  • c++

/** * 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(a);vector<int> tmp(len, 0);
            for(int i = 0; i < len; i++) {
                root = q.front(a); q.pop(a); 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; }returnans; }};Copy the code

In functional languages, flatMap can be used to easily get the set of nodes of the next layer, and map can get the set of nodes of the current layer val.

  • kotlin

Tailrec Fun zigzagLevelOrder:

Ans: List > : the current cumulative result

List: list
: current layer node.

Reverse: Boolean: Indicates whether to reverse order

If there are no nodes in the current layer, it is done. Return ans; Otherwise, ans + the collection of the current layer node val is the new cumulative result, and list.flatmap {it -> listOfNotNull(it. Left, it. Right)} gets the collection of non-empty nodes of the next layer and starts calling the next layer

So you can go one line, one stroke.

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() elseit }), list.flatMap { listOfNotNull(it.left, it.right) }, ! reverse)Copy the code
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() elseit }), list.flatMap { listOfNotNull(it.left, it.right) }, ! reverse )return zigzagLevelOrder(emptyList(), listOf(root), false)}}Copy the code

  • scala

One knife flow

@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)

Copy the code
/** * 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)}}Copy the code
  • rust

Rust is a poor use of this data structure. In particular, one stroke stream can be longer than the normal writing method, because the function stack consumes more memory. If the algorithm complexity is the same, there is no difference in time between the two methods

// A knife stream curly braces cannot be saved, resulting in a very long
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(refright) = i.borrow().right { acc.push(right.clone()) } acc }), ! reverse, ) } } zigzag_level_order(vec![].vec![i], false)}else {
            vec![]}}}Copy the code