题目
1- 思路
二叉树的层序遍历,遇到奇数时,利用 Collections.reverse()
翻转即可
2- 实现
⭐103. 二叉树的锯齿形层序遍历——题解思路
class Solution { public List < List < Integer > > res = new ArrayList < > ( ) ; public List < List < Integer > > zigzagLevelOrder ( TreeNode root) { return Traversal ( root) ; } public List < List < Integer > > Traversal ( TreeNode root) { if ( root== null ) { return res; } Queue < TreeNode > queue = new LinkedList < > ( ) ; queue. offer ( root) ; int count = 0 ; while ( ! queue. isEmpty ( ) ) { int len = queue. size ( ) ; List < Integer > path = new ArrayList < > ( ) ; while ( len> 0 ) { TreeNode node = queue. poll ( ) ; path. add ( node. val) ; if ( node. left!= null ) { queue. offer ( node. left) ; } if ( node. right!= null ) { queue. offer ( node. right) ; } len-- ; } count++ ; if ( count% 2 == 1 ) { res. add ( new ArrayList ( path) ) ; } else { Collections . reverse ( path) ; res. add ( new ArrayList ( path) ) ; } } return res; }
}
2- ACM实现
public class levelTraversal { static class TreeNode { int val; TreeNode left; TreeNode right; TreeNode ( ) { } TreeNode ( int x) { val = x; } } public static TreeNode build ( Integer [ ] nums) { Queue < TreeNode > queue = new LinkedList < > ( ) ; TreeNode root = new TreeNode ( nums[ 0 ] ) ; queue. offer ( root) ; int index = 1 ; while ( ! queue. isEmpty ( ) && index< nums. length) { TreeNode node = queue. poll ( ) ; if ( nums[ index] != null && index< nums. length) { node. left = new TreeNode ( nums[ index] ) ; queue. offer ( node. left) ; } index++ ; if ( nums[ index] != null && index< nums. length) { node. right = new TreeNode ( nums[ index] ) ; queue. offer ( node. right) ; } index++ ; } return root; } static List < List < Integer > > res = new ArrayList < > ( ) ; public static List < List < Integer > > levelTraversal ( TreeNode root) { if ( root== null ) { return res; } Queue < TreeNode > queue = new LinkedList < > ( ) ; queue. offer ( root) ; int level = 0 ; while ( ! queue. isEmpty ( ) ) { List < Integer > iterm = new ArrayList < > ( ) ; int len = queue. size ( ) ; while ( len> 0 ) { TreeNode node = queue. poll ( ) ; iterm. add ( node. val) ; if ( node. left!= null ) { queue. offer ( node. left) ; } if ( node. right!= null ) { queue. offer ( node. right) ; } len-- ; } if ( level% 2 == 1 ) { Collections . reverse ( iterm) ; } res. add ( new ArrayList < > ( iterm) ) ; } return res; } public static void main ( String [ ] args) { Scanner sc = new Scanner ( System . in) ; String input = sc. nextLine ( ) ; input = input. replace ( "[" , "" ) ; input = input. replace ( "]" , "" ) ; String [ ] parts = input. split ( "," ) ; Integer [ ] nums = new Integer [ parts. length] ; for ( int i = 0 ; i < parts. length ; i++ ) { if ( ! parts[ i] . equals ( "null" ) ) { nums[ i] = Integer . parseInt ( parts[ i] ) ; } else { nums[ i] = null ; } } TreeNode root = build ( nums) ; levelTraversal ( root) ; System . out. println ( "结果为" + res. toString ( ) ) ; }
}