题目描述
给定一个二叉树,返回其节点值的锯齿形层次遍历。(即先从左往右,再从右往左进行下一层遍历,以此类推,层与层之间交替进行)。
示例:
例如:
给定二叉树: [3,9,20,null,null,15,7],
3
/ \
9 20
/ \
15 7
返回其层次遍历结果:
[
[3],
[9,20],
[15,7]
]
思路
1.思路与102.树的层次遍历相似,只不过需要隔层翻转。
2.可以设置一个翻转标识位flag,当falg == true时,进行头插法,这样便实现了翻转。
Java代码实现
public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
List<List<Integer>> res = new ArrayList<>();
LinkedList<TreeNode> nodes = new LinkedList<>();
List<Integer> curVals = new ArrayList<>();
int curMax = 1;
int count = 0;
if(root != null)
nodes.add(root);
//true : 反向压入值 false :正向压入值
boolean flag = false;
while(!nodes.isEmpty()){
TreeNode cur = nodes.pollFirst();
if(flag)
curVals.add(0,cur.val);
else
curVals.add(cur.val);
count++;
if(cur.left != null)
nodes.add(cur.left);
if(cur.right != null)
nodes.add(cur.right);
if(count == curMax){
curMax = nodes.size();
count = 0;
res.add(new ArrayList<>(curVals));
curVals = new ArrayList<>();
flag = !flag;
}
}
return res;
}
Golang代码实现
func levelOrder(root *TreeNode) [][]int {
res := make([][]int,0)
cur := make([]int,0)
nodeList := list.New()
if root != nil {
nodeList.PushBack(root)
}
count := 0
max := 1
flag := false
for nodeList.Len() > 0 {
curNode := nodeList.Front().Value.(*TreeNode)
nodeList.Remove(nodeList.Front())
cur = append(cur, curNode.Val)
count++
if curNode.Left != nil {
nodeList.PushBack(curNode.Left)
}
if curNode.Right != nil {
nodeList.PushBack(curNode.Right)
}
if count == max {
if flag {
cur = reverseSlice(cur)
}
flag = !flag
res = append(res,cur)
count = 0
max = nodeList.Len()
cur = make([]int,0)
}
}
return res
}
func reverseSlice(ori []int) []int {
for i,j := 0,len(ori)-1 ; i<j ;i,j = i+1,j-1 {
ori[i],ori[j] = ori[j],ori[i]
}
return ori
}
有疑问加站长微信联系(非本文作者)