代码随想录算法训练营day16 | 题目226、题目101、题目100、题目222、题目559
题目一描述
给你一棵二叉树的根节点 root ，翻转这棵二叉树，并返回其根节点。
示例 1：
输入：root = [4,2,7,1,3,6,9]
输出：[4,7,2,9,6,3,1]
示例 2：
输入：root = [2,1,3]
输出：[2,3,1]
示例 3：
输入：root = []
输出：[]
提示：
树中节点数目范围在 [0, 100] 内
-100 <= Node.val <= 100
解题思路
bfs，dfs均可
代码实现
方法一：
/**
* 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 TreeNode invertTree(TreeNode root) {
if (root == null) {
return root;
}
Queue<TreeNode> queue = new ArrayDeque<>();
queue.offer(root);
while (!queue.isEmpty()) {
int length = queue.size();
while (length > 0) {
TreeNode tempRoot = queue.poll();
TreeNode temp = tempRoot.left;
tempRoot.left = tempRoot.right;
tempRoot.right = temp;
if (tempRoot.left != null)
queue.offer(tempRoot.left);
if (tempRoot.right != null)
queue.offer(tempRoot.right);
length--;
}
}
return root;
}
}
方法二：
class Solution {
public TreeNode invertTree(TreeNode root) {
if (root == null) {
return root;
}
TreeNode temp = root.left;
root.left = root.right;
root.right = temp;
invertTree(root.left);
invertTree(root.right);
return root;
}
}
技巧总结
题目二描述
101. 对称二叉树
给你一个二叉树的根节点 root ， 检查它是否轴对称。
示例 1：
输入：root = [1,2,2,3,4,4,3]
输出：true
示例 2：
s输入：root = [1,2,2,null,3,null,3]
输出：false
提示：
树中节点数目在范围 [1, 1000] 内
-100 <= Node.val <= 100
进阶：你可以运用递归和迭代两种方法解决这个问题吗？
解题思路
思路一，null补位为完美二叉树，然后逐层元素入栈出栈对比。
思路二，逐层比较，使用队列，每次从两侧向中间先入队列，出队列每次出两个来比较是否相等，然后再入队列。（注意已经不是层序遍历了）
思路三，同时从左子树和右子树开始对称的dfs，同时比较
代码实现
方法一：
class Solution {
public boolean isSymmetric(TreeNode root) {
Queue<TreeNode> queue = new ArrayDeque<>();
Deque<TreeNode> stack = new LinkedList<>();
queue.offer(root);
while (!queue.isEmpty()) {
int length = queue.size();
for (int i = 0; i < length; i++) {
TreeNode temp = queue.poll();
TreeNode templeft;
TreeNode tempright;
if (temp.left != null) {
queue.offer(temp.left);
templeft = temp.left;
} else {
templeft = new TreeNode(Integer.MAX_VALUE);
}
if (length == 1 || i < length / 2) {
stack.push(templeft);
} else if (stack.pop().val != templeft.val) {
return false;
}
if (temp.right != null) {
queue.offer(temp.right);
tempright = temp.right;
} else {
tempright = new TreeNode(Integer.MAX_VALUE);
}
if (i < length / 2) {
stack.push(tempright);
} else if (stack.pop().val != tempright.val) {
return false;
}
}
}
return true;
}
}
方法二：
class Solution {
public boolean isSymmetric(TreeNode root) {
Queue<TreeNode> queue = new LinkedList<>();
queue.offer(root.left);
queue.offer(root.right);
while (!queue.isEmpty()) {
TreeNode left = queue.poll();
TreeNode right = queue.poll();
if (left == null && right == null) {
continue;
}
if (right == null || left == null || left.val != right.val) {
return false;
}
queue.offer(left.left);
queue.offer(right.right);
queue.offer(left.right);
queue.offer(right.left);
}
return true;
}
}
方法三：
class Solution {
public boolean isSymmetric(TreeNode root) {
return dfs(root.left, root.right);
}
public boolean dfs(TreeNode left, TreeNode right) {
if(left == null && right == null)
return true;
if(left == null || right == null || left.val != right.val)
return false;
return (dfs(left.left, right.right) && dfs(left.right, right.left));
}
}
题目三描述
给你两棵二叉树的根节点 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] 内
-10^4 <= Node.val <= 10^4
解题思路
递归同步比较左右子树节点即可
迭代可以用bfs，但是与层序无关，代码可以简化，每次取前两个结点比较，注意入队顺序即可。
代码实现
方法一：
class Solution {
public boolean isSameTree(TreeNode p, TreeNode q) {
if(p == null && q == null){
return true;
}
if(p == null || q == null || q.val != p.val){
return false;
}
return isSameTree(p.left, q.left) && isSameTree(p.right, q.right);
}
}
方法二：
class Solution {
public boolean isSameTree(TreeNode p, TreeNode q) {
Queue<TreeNode> queue = new LinkedList<>();
queue.offer(p);
queue.offer(q);
while (!queue.isEmpty()) {
TreeNode temp1 = queue.poll();
TreeNode temp2 = queue.poll();
if (temp1 == null && temp2 == null) {
continue;
}
if (temp1 == null || temp2 == null || temp1.val != temp2.val) {
return false;
}
queue.offer(temp1.left);
queue.offer(temp2.left);
queue.offer(temp1.right);
queue.offer(temp2.right);
}
return true;
}
}
题目四描述
给你一棵 完全二叉树 的根节点 root ，求出该树的节点个数。
完全二叉树 的定义如下：在完全二叉树中，除了最底层节点可能没填满外，其余每层节点数都达到最大值，并且最下面一层的节点都集中在该层最左边的若干位置。若最底层为第 h 层，则该层包含 1~ 2^h 个节点。
示例 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) 的简单解决方案。你可以设计一个更快的算法吗？
解题思路
注意完全二叉树的定义，完全二叉树是一棵满二叉树，或者最后一层的叶子结点不满，注意左子树不一定为满二叉树。
单个结点也算一棵满二叉树。
可以利用满二叉树的特点，在完全二叉树中，如果递归向左遍历的深度等于递归向右遍历的深度，那说明就是满二叉树，就可以直接用高度套公式求出来，否则继续递归寻找到满二叉树（也可以是最下面的结点）
仅对满二叉树有了计算上的优化，不是满二叉树的仍然是要计算左右子树的各自节点数量然后加一。
代码实现
方法一：
// 普通方法
class Solution {
public int countNodes(TreeNode root) {
if (root == null)
return 0;
return countNodes(root.left) + countNodes(root.right) + 1;
}
}
方法二：
class Solution {
public int countNodes(TreeNode root) {
if (root == null)
return 0;
int leftHeight = 1; // 不为空的结点本身高度就是1
int rightHeight = 1;
TreeNode tempLeft = root.left;
TreeNode tempRight = root.right;
while (tempLeft != null) {
leftHeight++;
tempLeft = tempLeft.left;
}
while (tempRight != null) {
rightHeight++;
tempRight = tempRight.right;
}
if (leftHeight == rightHeight) {
return (int) Math.pow(2, leftHeight) - 1; // 结点数量2^n - 1, n是高度
}
return countNodes(root.left) + countNodes(root.right) + 1;
}
}
技巧总结
学会Math.pow(x, n) 计算 x 的 n 次方，注意数据类型转换
题目五描述
给定一个 N 叉树，找到其最大深度。
最大深度是指从根节点到最远叶子节点的最长路径上的节点总数。
N 叉树输入按层序遍历序列化表示，每组子节点由空值分隔（请参见示例）。
示例 1：
输入：root = [1,null,3,2,4,null,5,6]
输出：3
示例 2：
输入：root = [1,null,2,3,4,5,null,null,6,7,null,8,null,9,10,null,null,11,null,12,null,13,null,null,14]
输出：5
提示：
树的深度不会超过 1000 。
树的节点数目位于 [0, 10^4] 之间。
解题思路
递归每次找到子结点的高度
代码实现
方法一：
class Solution {
public int maxDepth(Node root) {
if (root == null)
return 0;
int subHeight = 0; // 找到最高的子结点高度
for (Node child : root.children) {
subHeight = Math.max(subHeight, maxDepth(child));
}
return subHeight + 1;
}
}
方法二：
class Solution {
public int maxDepth(Node root) {
if (root == null)
return 0;
Queue<Node> queue = new ArrayDeque<>();
queue.offer(root);
int depth = 0;
while (!queue.isEmpty()) {
int length = queue.size();
while (length > 0) {
Node temp = queue.poll();
if (temp.children != null) {
for (Node child : temp.children) {
queue.offer(child);
}
}
length--;
}
depth++;
}
return depth;
}
}
