题目描述
给定一个二叉树,返回其节点值的锯齿形层次遍历。(即先从左往右,再从右往左进行下一层遍历,以此类推,层与层之间交替进行)。
示例:
例如: 给定二叉树: [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 }