c/c++开发分享C++实现LeetCode(103.二叉树的之字形层序遍历)

[leetcode] 103. binary tree zigzag level order traversal 二叉树的之字形层序遍历given a binary tree, return the&


[leetcode] 103. binary tree zigzag level order traversal 二叉树的之字形层序遍历

given a binary tree, return thzigzag level order traversal of its nodes’ values. (ie, from left to right, then right to left for the next level and alternate between).

for example:
given binary tree [3,9,20,null,null,15,7],

    3
/
9  20

15   7

return its zigzag level order traversal as:

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

这道二叉树的之字形层序遍历是之前那道 binary tree level order traversal 的变形,不同之处在于一行是从左到右遍历,下一行是从右往左遍历,交叉往返的之字形的层序遍历。最简单直接的方法就是利用层序遍历,并使用一个变量 cnt 来统计当前的层数(从0开始),将所有的奇数层的结点值进行翻转一下即可,参见代码如下:

解法一:

%ignore_pre_1%

我们可以将上面的解法进行优化一下,翻转数组虽然可行,但是比较耗时,假如能够直接计算出每个结点值在数组中的坐标,就可以直接进行更新了。由于每层的结点数是知道的,就是队列的元素个数,所以可以直接初始化数组的大小。此时使用一个变量 lefttoright 来标记顺序,初始时是 true,当此变量为 true 的时候,每次加入数组的位置就是i本身,若变量为 false 了,则加入到 size-1-i 位置上,这样就直接相当于翻转了数组。每层遍历完了之后,需要翻转 lefttoright 变量,同时不要忘了将 onelevel 加入结果 res,参见代码如下:

解法二:

  class solution {  public:      vector<vector<int>> zigzaglevelorder(treenode* root) {          if (!root) return {};          vector<vector<int>> res;          queue<treenode*> q{{root}};          bool lefttoright = true;          while (!q.empty()) {              int size = q.size();              vector<int> onelevel(size);              for (int i = 0; i < size; ++i) {                  treenode *t = q.front(); q.pop();                  int idx = lefttoright ? i : (size - 1 - i);                  onelevel[idx] = t->val;                  if (t->left) q.push(t->left);                  if (t->right) q.push(t->right);              }              lefttoright = !lefttoright;              res.push_back(onelevel);          }          return res;      }  };

我们也可以使用递归的方法来解,这里实际上用的是先序遍历,递归函数需要一个变量 level 来记录当前的深度,由于 level 是从0开始的,假如结果 res 的大小等于 level,就需要在结果 res 中新加一个空集,这样可以保证 res[level] 不会越界。取出 res[level] 之后,判断 levle 的奇偶,若其为偶数,则将 node->val 加入 onelevel 的末尾,若为奇数,则加在 onelevel 的开头。然后分别对 node 的左右子结点调用递归函数,此时要传入 level+1 即可,参见代码如下:

解法三:

  class solution {  public:      vector<vector<int>> zigzaglevelorder(treenode* root) {          vector<vector<int>> res;          helper(root, 0, res);          return res;      }      void helper(treenode* node, int level, vector<vector<int>>& res) {          if (!node) return;          if (res.size() <= level) {              res.push_back({});          }          vector<int> &onelevel = res[level];          if (level % 2 == 0) onelevel.push_back(node->val);          else onelevel.insert(onelevel.begin(), node->val);          helper(node->left, level + 1, res);          helper(node->right, level + 1, res);      }  };

github 同步地址:

类似题目:

binary tree level order traversal

参考资料:

https://leetcode.com/problems/binary-tree-zigzag-level-order-traversal/discuss/33815/my-accepted-java-solution

https://leetcode.com/problems/binary-tree-zigzag-level-order-traversal/discuss/33825/c%2b%2b-5ms-version%3a-one-queue-and-without-reverse-operation-by-using-size-of-each-level

到此这篇关于c++实现leetcode(103.二叉树的之字形层序遍历)的文章就介绍到这了,更多相关c++实现二叉树的之字形层序遍历内容请搜索<猴子技术宅>以前的文章或继续浏览下面的相关文章希望大家以后多多支持<猴子技术宅>!

需要了解更多c/c++开发分享C++实现LeetCode(103.二叉树的之字形层序遍历),都可以关注C/C++技术分享栏目—猴子技术宅(www.ssfiction.com)

本文来自网络收集,不代表猴子技术宅立场,如涉及侵权请点击右边联系管理员删除。

如若转载,请注明出处:https://www.ssfiction.com/c-cyuyankaifa/675075.html

发表评论

邮箱地址不会被公开。 必填项已用*标注