方法1使用1个队列
class Solution {//使用一个队列,如果一个队列可以解决,那么就不需要使用2个数组//要最下面一层的最左边的结点,那么就先入右结点再入左结点public int findBottomLeftValue(TreeNode root) {TreeNode node = root;Deque<TreeNode> dq = new ArrayDeque<>();dq.offer(root);while(dq.size()>0){node = dq.poll();if (node.right != null) dq.add(node.right);if (node.left != null) dq.add(node.left);}return node.val;}
}
方法2使用2个数组
class Solution {//使用2个数组,cur放当前层节点,next放下一层的结点,最后通过ans.size()%2>0来决定是否进行倒置public List<List<Integer>> zigzagLevelOrder(TreeNode root) {if(root==null) return new ArrayList<>();List<List<Integer>> ans = new ArrayList<>();List<TreeNode> cur = List.of(root);while(cur.size()>0){List<TreeNode> next = new ArrayList<>();List<Integer> vals = new ArrayList<>();for(TreeNode node : cur){vals.add(node.val);if(node.left!=null) next.add(node.left);if(node.right!=null) next.add(node.right);}cur = next;if(ans.size()%2>0) Collections.reverse(vals);ans.add(vals);}return ans; }
}