本文主要是介绍Binary Tree Zigzag Level Order Traversal问题及解法,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
问题描述:
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).
示例:
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问题及解法 的解法类似,只不过做了一下元素插入顺序的处理。
过程详见代码:
/*** 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) {vector<vector<int>> res;if (root == NULL) return res;bl(root, res, 0);return res;}void bl(TreeNode* root, vector<vector<int>>& res, int depth){if (root == NULL) return;if (res.size() <= depth)res.push_back(vector<int>());if (depth % 2 == 0)res[depth].push_back(root->val);else res[depth].insert(res[depth].begin(),root->val);bl(root->left, res, depth + 1);bl(root->right, res, depth + 1);}
};
这篇关于Binary Tree Zigzag Level Order Traversal问题及解法的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!