每日两题 103二叉树的锯齿形层序遍历（数组） 513找树左下角的值（队列）

103

题目

103
给你二叉树的根节点 root ，返回其节点值的 锯齿形层序遍历 。（即先从左往右，再从右往左进行下一层遍历，以此类推，层与层之间交替进行）。

示例 1：

输入：root = [3,9,20,null,null,15,7]
输出：[[3],[20,9],[15,7]]
示例 2：

输入：root = [1]
输出：[[1]]
示例 3：

输入：root = []
输出：[]

题解

/*** Definition for a binary tree node.* public class TreeNode {*     int val;*     TreeNode left;*     TreeNode right;*     TreeNode() {}*     TreeNode(int val) { this.val = val; }*     TreeNode(int val, TreeNode left, TreeNode right) {*         this.val = val;*         this.left = left;*         this.right = right;*     }* }*/
class Solution {public List<List<Integer>> zigzagLevelOrder(TreeNode root) {if (root == null) {return List.of();}List<List<Integer>> ans = new ArrayList<>();List<TreeNode> cur = new ArrayList<>();boolean even = false;cur.add(root);while (!cur.isEmpty()) {List<TreeNode> nxt = new ArrayList<>(cur.size());List<Integer> vals = new ArrayList<>();for (TreeNode node : cur) {vals.add(node.val);if (node.left != null) nxt.add(node.left);if (node.right != null) nxt.add(node.right);}cur = nxt;if (even) Collections.reverse(vals);ans.add(vals);even = !even;}return ans;}
}

513

题目

513
给定一个二叉树的 根节点 root，请找出该二叉树的 最底层 最左边 节点的值。

假设二叉树中至少有一个节点。

示例 1:

输入: root = [2,1,3]
输出: 1
示例 2:

输入: [1,2,3,4,null,5,6,null,null,7]
输出: 7

题解

/*** Definition for a binary tree node.* public class TreeNode {*     int val;*     TreeNode left;*     TreeNode right;*     TreeNode() {}*     TreeNode(int val) { this.val = val; }*     TreeNode(int val, TreeNode left, TreeNode right) {*         this.val = val;*         this.left = left;*         this.right = right;*     }* }*/
class Solution {public int findBottomLeftValue(TreeNode root) {TreeNode node = root;Queue<TreeNode> q = new ArrayDeque<>();q.add(root);while (!q.isEmpty()) {node = q.poll();if (node.right != null) q.add(node.right);if (node.left != null) q.add(node.left);}return node.val;}
}