Binary Tree Zigzag Level Order Traversal
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).
For example:
Given binary tree {3,9,20,#,#,15,7},
3
/ \
9 20
/ \
15 7
return its zigzag level order traversal as:
[
[3],
[20,9],
[15,7]
]
思路
递归，vector,前插和后插
解题
c++版1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30/**
* 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>> result;
bool flag=true;
inOrder(root,1,result,flag);
return result;
}
void inOrder(TreeNode *root,int level,vector<vector<int>>&result,bool flag){
if(!root) return;
if(level>result.size())
result.push_back(vector<int>());
if(flag)
result[level-1].push_back(root->val);
else
result[level-1].insert(result[level-1].begin(),root->val);
inOrder(root->left,level+1,result,!flag);
inOrder(root->right,level+1,result,!flag);
}
};
python版1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
# @param {TreeNode} root
# @return {integer[][]}
def zigzagLevelOrder(self, root):
result=[]
flag=True
self.inOrder(root,1,result,flag)
return result
def inOrder(self,root,level,result,flag):
if(not root):
return
if(level>len(result)):
s=[]
result.append(s)
if(flag):
result[level-1].append(root.val)
else:
result[level-1].insert(0,root.val)
self.inOrder(root.left,level+1,result,not flag)
self.inOrder(root.right,level+1,result,not flag)
