[leetcode] 103. Binary Tree Zigzag Level Order Traversal

[leetcode] 103. Binary Tree Zigzag Level Order Traversal

Description

Given a binary tree, return the zigzag 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]]

分析一

题目的意思是：实现树的之字形遍历。 方法一是用双向队列，题目本身难度比较小，注意分情况讨论就行了。

代码一

/** * Definition for binary tree * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */class Solution {public: vector > zigzagLevelOrder(TreeNode *root) { vector > result; if(root==NULL) return result; deque q1; TreeNode *temp; q1.push_back(root); int zz=0; while(!q1.empty()){ int len=q1.size(); vector ans; for(int i=0;ival); q1.pop_front(); if(temp->right){ q1.push_back(temp->right); } if(temp->left){ q1.push_back(temp->left); } }else{ temp=q1.back(); ans.push_back(temp->val); q1.pop_back(); if(temp->left){ q1.push_front(temp->left); } if(temp->right){ q1.push_front(temp->right); } } } zz++; result.push_back(ans); } return result; }};

分析二

比起双向队列，我觉得双栈的操作很有趣，我比较推崇第二种方法。

代码二

/** * 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> zigzagLevelOrder(TreeNode* root) { vector> res; if(!root){ return res; } stack s1; stack s2; s1.push(root); while(s1.size()||s2.size()){ vector ans; while(!s1.empty()){ TreeNode* cur=s1.top(); ans.push_back(cur->val); s1.pop(); if(cur->left){ s2.push(cur->left); } if(cur->right){ s2.push(cur->right); } } if(ans.size()){ res.push_back(ans); } ans.clear(); while(!s2.empty()){ TreeNode* cur=s2.top(); ans.push_back(cur->val); s2.pop(); if(cur->right){ s1.push(cur->right); } if(cur->left){ s1.push(cur->left); } } if(ans.size()){ res.push_back(ans); } } return res; }};

参考文献

​​[编程题]binary-tree-zigzag-level-order-traversal​​​​[LeetCode] Binary Tree Zigzag Level Order Traversal 二叉树的之字形层序遍历​​

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。