目录
九、二叉树
68. 二叉树的最大深度 ① ×
69. 相同的树 ① √
70. 翻转二叉树 ① ×
71. 对称二叉树 ① ×
72. 从前序与中序遍历序列构造二叉树 ② ×
73. 从中序与后续遍历序列构造二叉树 ②
74. 填充每个节点的下一个右侧节点指针 II ② ×
75. 二叉树展开为链表 ② ×
76. 路径总和 ① ×
77. 求根节点到叶节点数字之和 ② ×
78. 二叉树中的最大路径和 ③
79. 二叉搜索树迭代器 ②
80. 完全二叉树的节点个数 ① √-
81. 二叉树的最近公共祖先 ②
十、二叉树层次遍历
82. 二叉树的右视图 ② ×
83. 二叉树的层平均值 ① √-
84. 二叉树的层序遍历 ② √
85. 二叉树的锯齿形层序遍历 ② √
十一、二叉搜索树
86. 二叉搜索树的最小绝对差 ①
87. 二叉搜索树中第K小的元素 ②
88. 验证二叉搜索树 ②
九、二叉树
68. 二叉树的最大深度 ① ×
给定一个二叉树 root ，返回其最大深度。
二叉树的 最大深度 是指从根节点到最远叶子节点的最长路径上的节点数。
示例 1：
输入：root = [3,9,20,null,null,15,7] 输出：3
示例 2：
输入：root = [1,null,2] 输出：2
提示：
- 树中节点的数量在
[0, 104]区间内。 -100 <= Node.val <= 100
思路分析：力扣（LeetCode）官网 - 全球极客挚爱的技术成长平台
方法2：（0ms）
public int maxDepth(TreeNode root) {
if (root == null) return 0;
return Math.max(maxDepth(root.left), maxDepth(root.right)) + 1;
}
作者：Krahets
链接：https://leetcode.cn/problems/maximum-depth-of-binary-tree/solutions/2361697/104-er-cha-shu-de-zui-da-shen-du-hou-xu-txzrx/
69. 相同的树 ① √
给你两棵二叉树的根节点 p 和 q ，编写一个函数来检验这两棵树是否相同。
如果两个树在结构上相同，并且节点具有相同的值，则认为它们是相同的。
示例 1：
输入：p = [1,2,3], q = [1,2,3] 输出：true
示例 2：
输入：p = [1,2], q = [1,null,2] 输出：false
示例 3：
输入：p = [1,2,1], q = [1,1,2] 输出：false
提示：
- 两棵树上的节点数目都在范围
[0, 100]内 -104 <= Node.val <= 104
方法1：（0ms）
public boolean isSameTree(TreeNode p, TreeNode q) {
if (p == null && q != null) {
return false;
} else if (p != null && q == null) {
return false;
} else if (p == null && q == null) {
return true;
} else if (p != null && q != null && p.val == q.val) {
if (isSameTree(p.left, q.left) && isSameTree(p.right, q.right)) {
return true;
} else {
return false;
}
} else if (p != null && q != null && p.val != q.val) {
return false;
} else {
return false;
}
}
方法2：力扣（LeetCode）官网 - 全球极客挚爱的技术成长平台
public boolean isSameTree(TreeNode p, TreeNode q) {
if(p == null && q == null)
return true;
if(p == null || q == null)
return false;
if(p.val != q.val)
return false;
return isSameTree(p.left, q.left) && isSameTree(p.right, q.right);
}
作者：画手大鹏
链接：https://leetcode.cn/problems/same-tree/solutions/12686/hua-jie-suan-fa-100-xiang-tong-de-shu-by-guanpengc/
70. 翻转二叉树 ① ×
给你一棵二叉树的根节点 root ，翻转这棵二叉树，并返回其根节点。
示例 1：
输入：root = [4,2,7,1,3,6,9] 输出：[4,7,2,9,6,3,1]
示例 2：
示例 3：
输入：root = [] 输出：[]
提示：
- 树中节点数目范围在
[0, 100]内 -100 <= Node.val <= 100
解析：力扣（LeetCode）官网 - 全球极客挚爱的技术成长平台
方法2：（0ms）
public TreeNode invertTree(TreeNode root) {
//递归函数的终止条件，节点为空时返回
if(root==null) {
return null;
}
//下面三句是将当前节点的左右子树交换
TreeNode tmp = root.right;
root.right = root.left;
root.left = tmp;
//递归交换当前节点的 左子树
invertTree(root.left);
//递归交换当前节点的 右子树
invertTree(root.right);
//函数返回时就表示当前这个节点，以及它的左右子树
//都已经交换完了
return root;
}
作者：王尼玛
链接：https://leetcode.cn/problems/invert-binary-tree/solutions/73159/dong-hua-yan-shi-liang-chong-shi-xian-226-fan-zhua/
方法3：（0ms）
public TreeNode invertTree(TreeNode root) {
if(root==null) {
return null;
}
//将二叉树中的节点逐层放入队列中，再迭代处理队列中的元素
LinkedList<TreeNode> queue = new LinkedList<TreeNode>();
queue.add(root);
while(!queue.isEmpty()) {
//每次都从队列中拿一个节点，并交换这个节点的左右子树
TreeNode tmp = queue.poll();
TreeNode left = tmp.left;
tmp.left = tmp.right;
tmp.right = left;
//如果当前节点的左子树不为空，则放入队列等待后续处理
if(tmp.left!=null) {
queue.add(tmp.left);
}
//如果当前节点的右子树不为空，则放入队列等待后续处理
if(tmp.right!=null) {
queue.add(tmp.right);
}
}
//返回处理完的根节点
return root;
}方法4：（0ms）
public TreeNode invertTree(TreeNode root) {
if (root == null)
return root;
TreeNode temp = root.left;
root.left = invertTree(root.right);
root.right = invertTree(temp);
return root;
}71. 对称二叉树 ① ×
给你一个二叉树的根节点 root ， 检查它是否轴对称。
示例 1：
输入：root = [1,2,2,3,4,4,3] 输出：true
示例 2：
输入：root = [1,2,2,null,3,null,3] 输出：false
提示：
- 树中节点数目在范围
[1, 1000]内 -100 <= Node.val <= 100
进阶：你可以运用递归和迭代两种方法解决这个问题吗？
题解思路：. - 力扣（LeetCode）
方法2：（0ms）
public boolean isSymmetric(TreeNode root) {
if(root==null) {
return true;
}
//调用递归函数，比较左节点，右节点
return dfs(root.left,root.right);
}
boolean dfs(TreeNode left, TreeNode right) {
//递归的终止条件是两个节点都为空
//或者两个节点中有一个为空
//或者两个节点的值不相等
if(left==null && right==null) {
return true;
}
if(left==null || right==null) {
return false;
}
if(left.val!=right.val) {
return false;
}
//再递归的比较 左节点的左孩子 和 右节点的右孩子
//以及比较 左节点的右孩子 和 右节点的左孩子
return dfs(left.left,right.right) && dfs(left.right,right.left);
}
作者：王尼玛
链接：https://leetcode.cn/problems/symmetric-tree/solutions/46560/dong-hua-yan-shi-101-dui-cheng-er-cha-shu-by-user7/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。方法3：
public boolean isSymmetric(TreeNode root) {
if(root==null || (root.left==null && root.right==null)) {
return true;
}
//用队列保存节点
LinkedList<TreeNode> queue = new LinkedList<TreeNode>();
//将根节点的左右孩子放到队列中
queue.add(root.left);
queue.add(root.right);
while(queue.size()>0) {
//从队列中取出两个节点，再比较这两个节点
TreeNode left = queue.removeFirst();
TreeNode right = queue.removeFirst();
//如果两个节点都为空就继续循环，两者有一个为空就返回false
if(left==null && right==null) {
continue;
}
if(left==null || right==null) {
return false;
}
if(left.val!=right.val) {
return false;
}
//将左节点的左孩子， 右节点的右孩子放入队列
queue.add(left.left);
queue.add(right.right);
//将左节点的右孩子，右节点的左孩子放入队列
queue.add(left.right);
queue.add(right.left);
}
return true;
}
作者：王尼玛
链接：https://leetcode.cn/problems/symmetric-tree/solutions/46560/dong-hua-yan-shi-101-dui-cheng-er-cha-shu-by-user7/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。72. 从前序与中序遍历序列构造二叉树 ② ×
给定两个整数数组 preorder 和 inorder ，其中 preorder 是二叉树的先序遍历， inorder 是同一棵树的中序遍历，请构造二叉树并返回其根节点。
示例 1:
输入: preorder = [3,9,20,15,7], inorder = [9,3,15,20,7] 输出: [3,9,20,null,null,15,7]
示例 2:
输入: preorder = [-1], inorder = [-1] 输出: [-1]
提示:
1 <= preorder.length <= 3000inorder.length == preorder.length-3000 <= preorder[i], inorder[i] <= 3000preorder和inorder均 无重复 元素inorder均出现在preorderpreorder保证 为二叉树的前序遍历序列inorder保证 为二叉树的中序遍历序列
题解：. - 力扣（LeetCode）
方法2：（1ms） . - 力扣（LeetCode）
int[] preorder;
HashMap<Integer, Integer> dic = new HashMap<>();
public TreeNode buildTree(int[] preorder, int[] inorder) {
this.preorder = preorder;
for(int i = 0; i < inorder.length; i++)
dic.put(inorder[i], i);
return recur(0, 0, inorder.length - 1);
}
TreeNode recur(int root, int left, int right) {
if (left > right) return null; // 递归终止
TreeNode node = new TreeNode(preorder[root]); // 建立根节点
int i = dic.get(preorder[root]); // 划分根节点、左子树、右子树
node.left = recur(root + 1, left, i - 1); // 开启左子树递归
node.right = recur(root + i - left + 1, i + 1, right); // 开启右子树递归
return node; // 回溯返回根节点
}
作者：Krahets
链接：https://leetcode.cn/problems/construct-binary-tree-from-preorder-and-inorder-traversal/solutions/2361558/105-cong-qian-xu-yu-zhong-xu-bian-li-xu-4lvkz/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。方法3：（1ms） 递归
. - 力扣（LeetCode）
private Map<Integer, Integer> indexMap;
public TreeNode myBuildTree(int[] preorder, int[] inorder, int preorder_left, int preorder_right, int inorder_left, int inorder_right) {
if (preorder_left > preorder_right) {
return null;
}
// 前序遍历中的第一个节点就是根节点
int preorder_root = preorder_left;
// 在中序遍历中定位根节点
int inorder_root = indexMap.get(preorder[preorder_root]);
// 先把根节点建立出来
TreeNode root = new TreeNode(preorder[preorder_root]);
// 得到左子树中的节点数目
int size_left_subtree = inorder_root - inorder_left;
// 递归地构造左子树，并连接到根节点
// 先序遍历中「从 左边界+1 开始的 size_left_subtree」个元素就对应了中序遍历中「从 左边界 开始到 根节点定位-1」的元素
root.left = myBuildTree(preorder, inorder, preorder_left + 1, preorder_left + size_left_subtree, inorder_left, inorder_root - 1);
// 递归地构造右子树，并连接到根节点
// 先序遍历中「从 左边界+1+左子树节点数目 开始到 右边界」的元素就对应了中序遍历中「从 根节点定位+1 到 右边界」的元素
root.right = myBuildTree(preorder, inorder, preorder_left + size_left_subtree + 1, preorder_right, inorder_root + 1, inorder_right);
return root;
}
public TreeNode buildTree(int[] preorder, int[] inorder) {
int n = preorder.length;
// 构造哈希映射，帮助我们快速定位根节点
indexMap = new HashMap<Integer, Integer>();
for (int i = 0; i < n; i++) {
indexMap.put(inorder[i], i);
}
return myBuildTree(preorder, inorder, 0, n - 1, 0, n - 1);
}
作者：力扣官方题解
链接：https://leetcode.cn/problems/construct-binary-tree-from-preorder-and-inorder-traversal/solutions/255811/cong-qian-xu-yu-zhong-xu-bian-li-xu-lie-gou-zao-9/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。方法4：（1ms） 迭代
public TreeNode buildTree(int[] preorder, int[] inorder) {
if (preorder == null || preorder.length == 0) {
return null;
}
TreeNode root = new TreeNode(preorder[0]);
Deque<TreeNode> stack = new LinkedList<TreeNode>();
stack.push(root);
int inorderIndex = 0;
for (int i = 1; i < preorder.length; i++) {
int preorderVal = preorder[i];
TreeNode node = stack.peek();
if (node.val != inorder[inorderIndex]) {
node.left = new TreeNode(preorderVal);
stack.push(node.left);
} else {
while (!stack.isEmpty() && stack.peek().val == inorder[inorderIndex]) {
node = stack.pop();
inorderIndex++;
}
node.right = new TreeNode(preorderVal);
stack.push(node.right);
}
}
return root;
}
作者：力扣官方题解
链接：https://leetcode.cn/problems/construct-binary-tree-from-preorder-and-inorder-traversal/solutions/255811/cong-qian-xu-yu-zhong-xu-bian-li-xu-lie-gou-zao-9/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。73. 从中序与后续遍历序列构造二叉树 ②
74. 填充每个节点的下一个右侧节点指针 II ② ×
给定一个二叉树：
struct Node {
int val;
Node *left;
Node *right;
Node *next;
}
填充它的每个 next 指针，让这个指针指向其下一个右侧节点。如果找不到下一个右侧节点，则将 next 指针设置为 NULL 。
初始状态下，所有 next 指针都被设置为 NULL 。
示例 1：
输入：root = [1,2,3,4,5,null,7] 输出：[1,#,2,3,#,4,5,7,#] 解释：给定二叉树如图 A 所示，你的函数应该填充它的每个 next 指针，以指向其下一个右侧节点，如图 B 所示。序列化输出按层序遍历顺序（由 next 指针连接），'#' 表示每层的末尾。
示例 2：
输入：root = [] 输出：[]
提示：
- 树中的节点数在范围
[0, 6000]内 -100 <= Node.val <= 100
进阶：
- 你只能使用常量级额外空间。
- 使用递归解题也符合要求，本题中递归程序的隐式栈空间不计入额外空间复杂度。
解题思路：. - 力扣（LeetCode）
方法2：（1ms）
public Node connect(Node root) {
if (root == null)
return root;
Queue<Node> queue = new LinkedList<>();
queue.add(root);
while (!queue.isEmpty()) {
//每一层的数量
int levelCount = queue.size();
//前一个节点
Node pre = null;
for (int i = 0; i < levelCount; i++) {
//出队
Node node = queue.poll();
//如果pre为空就表示node节点是这一行的第一个，
//没有前一个节点指向他，否则就让前一个节点指向他
if (pre != null) {
pre.next = node;
}
//然后再让当前节点成为前一个节点
pre = node;
//左右子节点如果不为空就入队
if (node.left != null)
queue.add(node.left);
if (node.right != null)
queue.add(node.right);
}
}
return root;
}
作者：数据结构和算法
链接：https://leetcode.cn/problems/populating-next-right-pointers-in-each-node-ii/solutions/429992/bfsjie-jue-zui-hao-de-ji-bai-liao-100de-yong-hu-by/
75. 二叉树展开为链表 ② ×
给你二叉树的根结点 root ，请你将它展开为一个单链表：
- 展开后的单链表应该同样使用
TreeNode，其中right子指针指向链表中下一个结点，而左子指针始终为null。 - 展开后的单链表应该与二叉树 先序遍历 顺序相同。
示例 1：
输入：root = [1,2,5,3,4,null,6] 输出：[1,null,2,null,3,null,4,null,5,null,6]
示例 2：
输入：root = [] 输出：[]
示例 3：
输入：root = [0] 输出：[0]
提示：
- 树中结点数在范围
[0, 2000]内 -100 <= Node.val <= 100
进阶：你可以使用原地算法（O(1) 额外空间）展开这棵树吗？
解题思路：. - 力扣（LeetCode）
方法2：（0ms）
public void flatten(TreeNode root) {
while (root != null) {
//左子树为 null，直接考虑下一个节点
if (root.left == null) {
root = root.right;
} else {
// 找左子树最右边的节点
TreeNode pre = root.left;
while (pre.right != null) {
pre = pre.right;
}
//将原来的右子树接到左子树的最右边节点
pre.right = root.right;
// 将左子树插入到右子树的地方
root.right = root.left;
root.left = null;
// 考虑下一个节点
root = root.right;
}
}
}
作者：windliang
链接：https://leetcode.cn/problems/flatten-binary-tree-to-linked-list/solutions/17274/xiang-xi-tong-su-de-si-lu-fen-xi-duo-jie-fa-by--26/
76. 路径总和 ① ×
给你二叉树的根节点 root 和一个表示目标和的整数 targetSum 。判断该树中是否存在 根节点到叶子节点 的路径，这条路径上所有节点值相加等于目标和 targetSum 。如果存在，返回 true ；否则，返回 false 。
叶子节点 是指没有子节点的节点。
示例 1：
输入：root = [5,4,8,11,null,13,4,7,2,null,null,null,1], targetSum = 22 输出：true 解释：等于目标和的根节点到叶节点路径如上图所示。
示例 2：
输入：root = [1,2,3], targetSum = 5 输出：false 解释：树中存在两条根节点到叶子节点的路径： (1 --> 2): 和为 3 (1 --> 3): 和为 4 不存在 sum = 5 的根节点到叶子节点的路径。
示例 3：
输入：root = [], targetSum = 0 输出：false 解释：由于树是空的，所以不存在根节点到叶子节点的路径。
提示：
- 树中节点的数目在范围
[0, 5000]内 -1000 <= Node.val <= 1000-1000 <= targetSum <= 1000
解题思路：. - 力扣（LeetCode）
方法2：（）
public boolean hasPathSum(TreeNode root, int sum) {
// 如果根节点为空，直接返回false
if (root == null) return false;
// 如果当前节点是叶子节点（即左右子节点都为空），检查路径和是否等于目标值
if (root.left == null && root.right == null) {
return sum == root.val;
}
// 如果当前节点不是叶子节点，递归地在左子树和右子树中查找路径
// 路径和等于目标值减去当前节点的值
return hasPathSum(root.left, sum - root.val) || hasPathSum(root.right, sum - root.val);
}方法2：（0ms）dfs
public boolean hasPathSum(TreeNode root, int sum) {
// 如果根节点为空，直接返回false
if (root == null) return false;
// 调用深度优先搜索（DFS）函数，查找是否存在一条从根节点到叶子节点的路径，使得路径上的节点值之和等于给定的目标值
return dfs(root, sum, root.val);
}
private boolean dfs(TreeNode root, int target, int pathSum) {
// 如果当前节点为空，直接返回false
if (root == null) return false;
// 如果路径和等于目标值，并且当前节点是叶子节点（即左右子节点都为空），返回true
if (pathSum == target && root.left == null && root.right == null) {
return true;
}
// 初始化左右子树的标志位为false
boolean leftFlag = false, rightFlag = false;
// 如果左子节点不为空，递归地在左子树中查找路径，路径和等于当前路径和加上左子节点的值
if (root.left != null) {
leftFlag = dfs(root.left, target, pathSum + root.left.val);
}
// 如果右子节点不为空，递归地在右子树中查找路径，路径和等于当前路径和加上右子节点的值
if (root.right != null) {
rightFlag = dfs(root.right, target, pathSum + root.right.val);
}
// 如果左子树或右子树中存在满足条件的路径，返回true，否则返回false
return leftFlag || rightFlag;
}77. 求根节点到叶节点数字之和 ② ×
给你一个二叉树的根节点 root ，树中每个节点都存放有一个 0 到 9 之间的数字。
每条从根节点到叶节点的路径都代表一个数字：
- 例如，从根节点到叶节点的路径
1 -> 2 -> 3表示数字123。
计算从根节点到叶节点生成的 所有数字之和 。
叶节点 是指没有子节点的节点。
示例 1：
输入：root = [1,2,3] 输出：25 解释： 从根到叶子节点路径 1->2 代表数字 12 从根到叶子节点路径 1->3 代表数字 13 因此，数字总和 = 12 + 13 = 25
示例 2：
输入：root = [4,9,0,5,1] 输出：1026 解释： 从根到叶子节点路径 4->9->5 代表数字 495 从根到叶子节点路径 4->9->1 代表数字 491从根到叶子节点路径 4->0 代表数字 40 因此，数字总和 = 495 + 491 + 40 = 1026 提示：
- 树中节点的数目在范围
[1, 1000]内 0 <= Node.val <= 9- 树的深度不超过
10
解题思路：. - 力扣（LeetCode）
方法2：（0ms）
public int sumNumbers(TreeNode root) {
return dfs(root, 0);
}
public int dfs(TreeNode root, int prevSum) {
if (root == null) {
return 0;
}
int sum = prevSum * 10 + root.val;
if (root.left == null && root.right == null) {
return sum;
} else {
return dfs(root.left, sum) + dfs(root.right, sum);
}
}
作者：力扣官方题解
链接：https://leetcode.cn/problems/sum-root-to-leaf-numbers/solutions/464666/qiu-gen-dao-xie-zi-jie-dian-shu-zi-zhi-he-by-leetc/
78. 二叉树中的最大路径和 ③
79. 二叉搜索树迭代器 ②
80. 完全二叉树的节点个数 ① √-
给你一棵 完全二叉树 的根节点 root ，求出该树的节点个数。
完全二叉树 的定义如下：在完全二叉树中，除了最底层节点可能没填满外，其余每层节点数都达到最大值，并且最下面一层的节点都集中在该层最左边的若干位置。若最底层为第 h 层，则该层包含 1~ 2h 个节点。
示例 1：
输入：root = [1,2,3,4,5,6] 输出：6
示例 2：
输入：root = [] 输出：0
示例 3：
输入：root = [1] 输出：1
提示：
- 树中节点的数目范围是
[0, 5 * 104] 0 <= Node.val <= 5 * 104- 题目数据保证输入的树是 完全二叉树
进阶：遍历树来统计节点是一种时间复杂度为 O(n) 的简单解决方案。你可以设计一个更快的算法吗？
力扣题解思路：
. - 力扣（LeetCode）
方法1：（7ms）
public int countNodes(TreeNode root) {
if (root == null){
return 0;
}
Deque<TreeNode> deque = new ArrayDeque<>();
deque.addLast(root);
int count = 1;
while (deque.size() > 0){
TreeNode newRoot = deque.remove();
TreeNode left = newRoot.left;
TreeNode right = newRoot.right;
if (left != null){
deque.addLast(left);
count++;
}
if (right != null){
deque.addLast(right);
count++;
}
}
return count;
}fangfa 2:（0ms）
public int countNodes(TreeNode root) {
if (root == null){
return 0;
}
return countNodes(root.left) + countNodes(root.right) + 1;
}
作者：Wanglihao
链接：https://leetcode.cn/problems/count-complete-tree-nodes/solutions/21544/chang-gui-jie-fa-he-ji-bai-100de-javajie-fa-by-xia/
81. 二叉树的最近公共祖先 ②
十、二叉树层次遍历
82. 二叉树的右视图 ② ×
给定一个二叉树的 根节点 root，想象自己站在它的右侧，按照从顶部到底部的顺序，返回从右侧所能看到的节点值。
示例 1:
输入: [1,2,3,null,5,null,4] 输出: [1,3,4]
示例 2:
输入: [1,null,3] 输出: [1,3]
示例 3:
输入: [] 输出: []
提示:
- 二叉树的节点个数的范围是
[0,100] -100 <= Node.val <= 100
方法2：（0ms） DFS
class Solution {
List<Integer> res = new ArrayList<>();
public List<Integer> rightSideView(TreeNode root) {
dfs(root, 0); // 从根节点开始访问，根节点深度是0
return res;
}
private void dfs(TreeNode root, int depth) {
if (root == null) {
return;
}
// 先访问 当前节点，再递归地访问 右子树 和 左子树。
if (depth == res.size()) { // 如果当前节点所在深度还没有出现在res里，说明在该深度下当前节点是第一个被访问的节点，因此将当前节点加入res中。
res.add(root.val);
}
depth++;
dfs(root.right, depth);
dfs(root.left, depth);
}
}
作者：Sweetiee 🍬
链接：https://leetcode.cn/problems/binary-tree-right-side-view/solutions/214871/jian-dan-bfsdfs-bi-xu-miao-dong-by-sweetiee/
方法3：（1ms） BFS
class Solution {
public List<Integer> rightSideView(TreeNode root) {
List<Integer> res = new ArrayList<>();
if (root == null) {
return res;
}
Queue<TreeNode> queue = new LinkedList<>();
queue.offer(root);
while (!queue.isEmpty()) {
int size = queue.size();
for (int i = 0; i < size; i++) {
TreeNode node = queue.poll();
if (node.left != null) {
queue.offer(node.left);
}
if (node.right != null) {
queue.offer(node.right);
}
if (i == size - 1) { //将当前层的最后一个节点放入结果列表
res.add(node.val);
}
}
}
return res;
}
}83. 二叉树的层平均值 ① √-
给定一个非空二叉树的根节点 root , 以数组的形式返回每一层节点的平均值。与实际答案相差 10-5 以内的答案可以被接受。
示例 1：
输入：root = [3,9,20,null,null,15,7] 输出：[3.00000,14.50000,11.00000] 解释：第 0 层的平均值为 3,第 1 层的平均值为 14.5,第 2 层的平均值为 11 。 因此返回 [3, 14.5, 11] 。
示例 2:
输入：root = [3,9,20,15,7] 输出：[3.00000,14.50000,11.00000]
提示：
- 树中节点数量在
[1, 104]范围内 -231 <= Node.val <= 231 - 1
题解：. - 力扣（LeetCode）
方法1：（2ms)
public static List<Double> averageOfLevels(TreeNode root) {
ArrayList<Double> list = new ArrayList<>();
if (root == null){
return list;
}
ArrayDeque<TreeNode> deque = new ArrayDeque<>();
deque.addLast(root);
list.add(new Double(root.val));
while (deque.size() > 0){
int size = deque.size();
double sum = 0;
int cnt = 0;
for (int i = 0; i < size; i++) {
TreeNode parent = deque.removeFirst();
TreeNode left = parent.left;
if (left != null){
deque.addLast(left);
sum += left.val;
cnt++;
}
TreeNode right = parent.right;
if (right != null){
deque.addLast(right);
sum += right.val;
cnt++;
}
}
if (cnt != 0) {
list.add(sum / cnt);
}
}
return list;
}84. 二叉树的层序遍历 ② √
给你二叉树的根节点 root ，返回其节点值的 层序遍历 。 （即逐层地，从左到右访问所有节点）。
示例 1：
输入：root = [3,9,20,null,null,15,7] 输出：[[3],[9,20],[15,7]]
示例 2：
输入：root = [1] 输出：[[1]]
示例 3：
输入：root = [] 输出：[] 解题思路：. - 力扣（LeetCode）
提示：
- 树中节点数目在范围
[0, 2000]内 -1000 <= Node.val <= 1000
方法1：（1ms）
public static List<List<Integer>> levelOrder(TreeNode root) {
ArrayList<List<Integer>> list = new ArrayList<>();
if (root == null){
return list;
}
ArrayDeque<TreeNode> deque = new ArrayDeque<>();
deque.addLast(root);
int count = 0;
ArrayList<Integer> subList = new ArrayList<>();
subList.add(root.val);
list.add(subList);
while (deque.size() > 0){
List<Integer> list1 = list.get(count);
int size = list1.size();
ArrayList<Integer> list2 = new ArrayList<>();
for (int i = 0; i < size; i++) {
TreeNode parent = deque.removeFirst();
TreeNode left = parent.left;
if (left != null){
deque.addLast(left);
list2.add(left.val);
}
TreeNode right = parent.right;
if (right != null){
deque.addLast(right);
list2.add(right.val);
}
}
if (list2.size() > 0) {
list.add(list2);
}
count++;
}
return list;
}
85. 二叉树的锯齿形层序遍历 ② √
给你二叉树的根节点 root ，返回其节点值的 锯齿形层序遍历 。（即先从左往右，再从右往左进行下一层遍历，以此类推，层与层之间交替进行）。
示例 1：
输入：root = [3,9,20,null,null,15,7] 输出：[[3],[20,9],[15,7]]
示例 2：
输入：root = [1] 输出：[[1]]
示例 3：
输入：root = [] 输出：[]
提示：
- 树中节点数目在范围
[0, 2000]内 -100 <= Node.val <= 100
解题思路：. - 力扣（LeetCode）
方法1：（0ms）
public static List<List<Integer>> zigzagLevelOrder(TreeNode root) {
ArrayList<List<Integer>> result = new ArrayList<>();
ArrayList<Integer> subList = new ArrayList<>();
if (root == null){
return result;
}
int count = 1;
subList.add(root.val);
result.add(subList);
ArrayList<TreeNode> nodeList = new ArrayList<>();
nodeList.add(root);
ArrayDeque<List<TreeNode>> deque = new ArrayDeque<>();
deque.addLast(nodeList);
while (true){
List<TreeNode> list = deque.remove();
ArrayList<TreeNode> newNodeList = new ArrayList<>();
ArrayList<Integer> newSubList = new ArrayList<>();
int size = list.size();
for (int i = 0; i < size; i++) {
TreeNode tailNode = list.get(size - i - 1);
TreeNode right = tailNode.right;
TreeNode left = tailNode.left;
if (count == 1){
if (right != null){
newNodeList.add(right);
newSubList.add(right.val);
}
if (left != null){
newNodeList.add(left);
newSubList.add(left.val);
}
}else {
if (left != null){
newNodeList.add(left);
newSubList.add(left.val);
}
if (right != null){
newNodeList.add(right);
newSubList.add(right.val);
}
}
}
count *= -1;
if (newNodeList.size() == 0){
break;
}else {
result.add(newSubList);
deque.addLast(newNodeList);
}
}
return result;
}
