目录
第一题：二叉树的镜像
我的答案：运行失败
class Solution {
public TreeNode mirrorTree(TreeNode root) {
LinkedListStack<TreeNode> stack=new LinkedListStack<>();
TreeNode curr=root;
while(curr!=null){
stack.push(curr);
curr=curr.left;
}
while(!stack.isEmpty()){
TreeNode pop=stack.pop();
root=pop.right;
}
return root;
}
}
//思路：
//前序遍历，把二叉树的节点压入栈中，从栈中弹出后就是后序遍历官方答案：
法一：递归（深度优先遍历，一竿子插到底）
class Solution {
public TreeNode mirrorTree(TreeNode root) {
if (root == null) {
return null;
}
TreeNode left = mirrorTree(root.left);//左指针，从左向右遍历二叉树
TreeNode right = mirrorTree(root.right);//右指针，从右开始遍历二叉对
root.left = right;//从叶子节点开始翻转，只需要交换子树的位置
root.right = left;
return root;
}
}网友答案：递归（深度优先遍历，一竿子插到底）
class Solution {
public TreeNode mirrorTree(TreeNode root) {
//递归函数的终止条件，节点为空时返回
if(root==null) {
return null;
}
//下面三句是将当前节点的左右子树交换
TreeNode tmp = root.right;
root.right = root.left;
root.left = tmp;
//递归交换当前节点的 左子树
mirrorTree(root.left);
//递归交换当前节点的 右子树
mirrorTree(root.right);
//函数返回时就表示当前这个节点，以及它的左右子树
//都已经交换完了
return root;
}
}网友答案：栈（迭代，广度优先遍历，层层遍历）
class Solution {
public TreeNode mirrorTree(TreeNode root) {
if(root == null) return null;
Stack<TreeNode> stack = new Stack<>() {{ add(root); }};//栈的初始值就是二叉树的根
while(!stack.isEmpty()) {
TreeNode node = stack.pop();//从根节点开始，遍历二叉树的每个节点，把它们的左、右节点压入栈中
//留在栈中的都是还没有交换左右子节点的，
if(node.left != null) stack.add(node.left);
if(node.right != null) stack.add(node.right);
TreeNode tmp = node.left;//交换每个节点node的左右子节点
node.left = node.right;
node.right = tmp;
}
return root;
}
}网友答案：队列（迭代，广度优先遍历，层层遍历）
class Solution {
public TreeNode mirrorTree(TreeNode root) {
if(root == null) return null;
Queue<TreeNode> queue = new LinkedList<TreeNode>();
TreeNode node = new TreeNode();//当前节点
TreeNode tmp = new TreeNode();//暂存节点
queue.offer(root);//根节点为队列的初始值
while(!queue.isEmpty()){
node = queue.poll();//从队列中取出节点
// 交换左右孩子，如果没有左右孩子，默认交换两个null孩子
tmp = node.left;
node.left = node.right;
node.right = tmp;
if(node.left != null){//把交换后的左节点存入队列中，等待着下一次去交换它的左右子节点
queue.offer(node.left);
}
if(node.right != null){
queue.offer(node.right);
}
}
return root;
}
}网友答案：队列（迭代，广度优先遍历，层层遍历）
class Solution {
public TreeNode mirrorTree(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;
}
}第二题：对称二叉树
我的答案：递归（运行失败）
class Solution {
public boolean isSymmetric(TreeNode root) {
if(root==null){
return true;
}
TreeNode root2=root;
TreeNode tmp=root.right;
root.right=root.left;
root.left=tmp;
if(root.left!=root2.left||root.right!=root2.right){
return false;
}
isSymmetric(root.left);
isSymmetric(root.right);
return true;
}
}官方答案：
法一：递归
class Solution {
public boolean isSymmetric(TreeNode root) {
return check(root, root);
}
public boolean check(TreeNode p, TreeNode q) {
if (p == null && q == null) {
return true;
}
if (p == null || q == null) {
return false;
}
return p.val == q.val && check(p.left, q.right) && check(p.right, q.left);
//p指针和 q 指针一开始都指向这棵树的根，随后 p 右移时，q左移，p左移时，q 右移。
//每次检查当前 p和 q 节点的值是否相等，如果相等再判断左右子树是否对称
}
}递归（大体结构）：
1、返回值和输入值
2、终止条件
3、单层递归
法二：迭代
class Solution {
public boolean isSymmetric(TreeNode root) {
return check(root, root);
}
public boolean check(TreeNode u, TreeNode v) {
Queue<TreeNode> q = new LinkedList<TreeNode>();
q.offer(u);//将左子树头结点加入队列
q.offer(v);//将右子树头结点加入队列
while (!q.isEmpty()) {
u = q.poll();//每次提取两个结点并比较它们的值
v = q.poll();
if (u == null && v == null) {
continue;
}
if ((u == null || v == null) || (u.val != v.val)) {
return false;
}
q.offer(u.left);
q.offer(v.right);
//u代表左子树，v代表右子树
q.offer(u.right);
q.offer(v.left);
//将两个结点的左右子结点按相反的顺序插入队列中
//相当于根节点的左边和右边同一层元素里，有两个相同的链表，有两个指针分别指向它们的头部和尾部，同时往中间移动，因为它们是镜像的，所以两个指针的值应该相等
}
return true;
}
}网友答案：
/**
* 递归法
*/
public boolean isSymmetric1(TreeNode root) {
return compare(root.left, root.right);
}
private boolean compare(TreeNode left, TreeNode right) {
if (left == null && right != null) {
return false;
}
if (left != null && right == null) {
return false;
}
if (left == null && right == null) {
return true;
}
if (left.val != right.val) {
return false;
}
// 比较外侧
boolean compareOutside = compare(left.left, right.right);
// 比较内侧
boolean compareInside = compare(left.right, right.left);
return compareOutside && compareInside;
}
/**
* 迭代法
* 使用双端队列，相当于两个栈
*/
public boolean isSymmetric2(TreeNode root) {
Deque<TreeNode> deque = new LinkedList<>();
deque.offerFirst(root.left);
deque.offerLast(root.right);
while (!deque.isEmpty()) {
TreeNode leftNode = deque.pollFirst();
TreeNode rightNode = deque.pollLast();
if (leftNode == null && rightNode == null) {
continue;
}
// if (leftNode == null && rightNode != null) {
// return false;
// }
// if (leftNode != null && rightNode == null) {
// return false;
// }
// if (leftNode.val != rightNode.val) {
// return false;
// }
// 以上三个判断条件合并
if (leftNode == null || rightNode == null || leftNode.val != rightNode.val) {
return false;
}
deque.offerFirst(leftNode.left);
deque.offerFirst(leftNode.right);
deque.offerLast(rightNode.right);
deque.offerLast(rightNode.left);
}
return true;
}
/**
* 迭代法
* 使用普通队列
*/
public boolean isSymmetric3(TreeNode root) {
Queue<TreeNode> deque = new LinkedList<>();
deque.offer(root.left);
deque.offer(root.right);
while (!deque.isEmpty()) {
TreeNode leftNode = deque.poll();
TreeNode rightNode = deque.poll();
if (leftNode == null && rightNode == null) {
continue;
}
// if (leftNode == null && rightNode != null) {
// return false;
// }
// if (leftNode != null && rightNode == null) {
// return false;
// }
// if (leftNode.val != rightNode.val) {
// return false;
// }
// 以上三个判断条件合并
if (leftNode == null || rightNode == null || leftNode.val != rightNode.val) {
return false;
}
// 这里顺序与使用Deque不同
deque.offer(leftNode.left);
deque.offer(rightNode.right);
deque.offer(leftNode.right);
deque.offer(rightNode.left);
}
return true;
}第三题：从上到下打印二叉树
官方答案：队列（先进先出）
class Solution {
public List<List<Integer>> levelOrder(TreeNode root) {
List<List<Integer>> ret = new ArrayList<List<Integer>>();//ret的底层原理是以level为键，对应节点值组成的数组为值的哈希表，往大list里存入一条条小list
if (root == null) {
return ret;
}
Queue<TreeNode> queue = new LinkedList<TreeNode>();//创建一个新队列
queue.offer(root);//根元素先入队
while (!queue.isEmpty()) {
List<Integer> level = new ArrayList<Integer>();//level表示该节点所在层数
int currentLevelSize = queue.size();//得到当前队列的长度，即为当层的节点数
for (int i = 1; i <= currentLevelSize; ++i) {
TreeNode node = queue.poll();//从队列弹出一个结点，然后下面把该结点的左右孩子压入队列（如果有的话）
level.add(node.val);//level是键，node.val是值，组成键值对。
if (node.left != null) {//左节点不为空时加入队列
queue.offer(node.left);
}
if (node.right != null) {//右节点不为空时加入队列
queue.offer(node.right);
}
}
ret.add(level);
}
return ret;
}
}
//while里面嵌套了一个for循环，while是遍历整棵二叉树的，for循环的范围则是一层的节点第四题：二叉树搜索树的第k大节点
我的答案：//运行失败
class Solution {
public int kthLargest(TreeNode root, int k) {
if(root==null){
return 0;
}
ArrayList list=new ArrayList();
while(root!=null){//把二叉树的节点值都存入数组list中
if(root.left!=null){
list.add(root.left.val);
}
if(root.right!=null){
list.add(root.right.val);
}
}
list.sort();//利用排序函数sort()
k=list.size()-k;//因为list是从小到大排序，而k是从大到小的次序
return list.get(k);
}
}
//把二叉树的值都存入数组中，再利用数组的排序sort()函数进行排序
//最后返回k网友答案：递归
class Solution {
int res, k;
public int kthLargest(TreeNode root, int k) {
this.k = k;
dfs(root);
return res;
}
void dfs(TreeNode root) {
//当前节点为第 k 大节点：每遍历到一个节点，将 k 值减1，直到 k 值为 0 ，
//说明找到第 k 大节点了，此时记录下节点的值，然后开始返回
if(root == null) return;//root 为 null 的时候，代表遍历到叶子节点了，此时需要返回
dfs(root.right);
if(k == 0) return;
if(--k == 0) res = root.val;
dfs(root.left);
}
}
- 二叉搜索树的特性就是中序遍历结果为递增序列，而题目要求的是第 k 大节点，所以就应该是要遍历结果为降序
- 按照
先遍历左子树、输出节点、遍历右子树得到的是升序结果，要得到降序，需要按照先遍历右子树、输出节点、再遍历左子树即可
网友答案：迭代（栈）
class Solution {
public int kthLargest(TreeNode root, int k) {
int count = 1;//计数器
Stack<TreeNode> stack = new Stack<>();
while (Objects.nonNull(root) || !stack.empty()) {//根节点不为空且栈不为空
while (Objects.nonNull(root)) {//把根节点和右节点压入栈，直到压入二叉树右下角的最大值（在栈顶）后才跳出这个while循环
stack.push(root);
root = root.right;
}
TreeNode pop = stack.pop();
if (count == k) {
return pop.val;
}
count++;
root = pop.left;
}
return 0;
}
}
第五题：二叉树的深度
我的答案：队列、广度优先 （模仿上面第三题：从上到下打印二叉树 的官方答案）
class Solution {
public int maxDepth(TreeNode root) {
if(root==null){
return 0;
}
Queue<TreeNode> queue=new LinkedList<>();
int level=0;//记录层数，即深度
queue.offer(root);
while(!queue.isEmpty()){//这个while循环用于遍历二叉树
int currentLevelSize=queue.size();//当前层的节点数
for(int i=1;i<=currentLevelSize;i++){//把当前层的全部节点压入队列
//一个一个吐出来，把吐出来的节点的左右节点压入队列中，排在后面，
//取够当前层的节点数后就不会再取了（后面压进的子节点不会在此时被取出）
TreeNode node=queue.poll();
if(node.left!=null){
queue.offer(node.left);
}
if(node.right!=null){
queue.offer(node.right);
}
}
level++;
}
return level;
}
}
官方答案：
法一：递归
class Solution {
public int maxDepth(TreeNode root) {
if (root == null) {//如果当前节点不为空，则返回
return 0;
} else {
int leftHeight = maxDepth(root.left);//最终返回左子树的最大深度
int rightHeight = maxDepth(root.right);//最终返回右子树的最大深度
return Math.max(leftHeight, rightHeight) + 1;//+1 是加上根节点的深度
}
}
}
法二：队列
class Solution {
public int maxDepth(TreeNode root) {
if (root == null) {
return 0;
}
Queue<TreeNode> queue = new LinkedList<TreeNode>();
queue.offer(root);
int ans = 0;
while (!queue.isEmpty()) {
int size = queue.size();
while (size > 0) {
TreeNode node = queue.poll();
if (node.left != null) {
queue.offer(node.left);
}
if (node.right != null) {
queue.offer(node.right);
}
size--;
}
ans++;
}
return ans;
}
}
第六题：平衡二叉树
我的答案：运行失败
//我的思路：如果左右节点中有一个为空，那另一个节点一定得是叶子节点
class Solution {
public boolean isBalanced(TreeNode root) {
if(root==null){
return true;
}
Queue<TreeNode> queue=new LinkedList<>();
queue.offer(root);
int level=0;
Boolean p=false;
while(!queue.isEmpty()){
int size=queue.size();
for(int i=1;i<=size;i++){
TreeNode node=queue.poll();
if(node.right!=null){
queue.offer(node.right);
}
if(node.left!=null){
queue.offer(node.left);
}
if(node.right==null&&node.left==null){
p=true;
continue;
}
if(node.right==null&&node.left!=null){
p=true;
queue.offer(node.left);
continue;
}
if(node.right!=null&&node.left==null){
p=true;
queue.offer(node.right);
continue;
}
}
if(p){
++level;
p=false;
if(level==3){
return false;
}
}
}
return true;
}
}官方答案：
法一：自顶向下的递归
class Solution {
public boolean isBalanced(TreeNode root) {
if (root == null) {
return true;
} else {
// Math.abs(height(root.left) - height(root.right))：计算该节点的左右子树高度差
//isBalanced(root.left) && isBalanced(root.right)：再分别递归左右节点，判断左右子树是否平衡
return Math.abs(height(root.left) - height(root.right)) <= 1 && isBalanced(root.left) && isBalanced(root.right);
}
}
public int height(TreeNode root) {//定义函数height，用于计算二叉树中的任意一个节点的高度
if (root == null) {//递到头了，准备回溯
return 0;
} else {
return Math.max(height(root.left), height(root.right)) + 1;//递进去后，回溯时节点的高度从返回的0值开始自增，最终得到节点的高度
}
}
}法二：自底向上的递归：
class Solution {
public boolean isBalanced(TreeNode root) {
return height(root) >= 0;//如果有子树是不平衡的，那整棵树一定是不平衡的
}
public int height(TreeNode root) {
if (root == null) {
return 0;
}
int leftHeight = height(root.left);//分别递归判断当前节点的左右子树是否平衡
int rightHeight = height(root.right);
if (leftHeight == -1 || rightHeight == -1 || Math.abs(leftHeight - rightHeight) > 1) {//以当前节点为根的子树不平衡，返回-1
return -1;
} else {//以当前节点为根的子树不平衡，返回其高度
return Math.max(leftHeight, rightHeight) + 1;
}
}
}网友答案：用flag优化，降低了时间和空间复杂度
class Solution {
boolean flag = true;
public boolean isBalanced(TreeNode root) {
deepTree(root);
return flag;
}
private int deepTree(TreeNode node) {
if(node == null || !flag) return 0;
int left = deepTree(node.left);
int right = deepTree(node.right);
if(Math.abs(left - right) > 1) flag = false;
return Math.max(left, right) + 1;
}
}第七题：二叉树的最近公共祖先
我的答案：运行失败
class Solution {
ArrayList<Integer> list=new ArrayList<>();
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
//递归找到了第一个目标节点
if(root!=p&&root!=null) {
lowestCommonAncestor(root,p,q);
//回溯时把它经过的节点值都存入数组中
list.add(root.val);
}
//递归找到了第二个目标节点
if(root!=q&&root!=null){
lowestCommonAncestor(root,p,q);
//回溯时和数组里的数进行比较
for(int i=1;i<=list.size();i++){
if(root.val==list.get(i)){
return root;
}
}
}
return root;
}
}
//报错：溢栈了官方答案：
法一：递归
class Solution {
private TreeNode ans;//储存最近的公共祖先
public Solution() {
this.ans = null;
}
private boolean dfs(TreeNode root, TreeNode p, TreeNode q) {
if (root == null) return false;
boolean lson = dfs(root.left, p, q);//root的左孩子
boolean rson = dfs(root.right, p, q);//root的右孩子
//(lson && rson)：root左右子树均包含p节点或q节点，一树一个
//(root.val == p.val || root.val == q.val)：root正好是p或q节点
//((root.val == p.val || root.val == q.val) && (lson || rson))：root正好是p或q节点且root的左或右子树有一个包含了另一个节点
if ((lson && rson) || ((root.val == p.val || root.val == q.val) && (lson || rson))) {
ans = root;
}
return lson || rson || (root.val == p.val || root.val == q.val);//root就是p或q节点，或者p或q节点就在root的左子树，或右子树
}
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
this.dfs(root, p, q);
return this.ans;
}
}法二：存储父节点
class Solution {
Map<Integer, TreeNode> parent = new HashMap<Integer, TreeNode>();
Set<Integer> visited = new HashSet<Integer>();//用链表也行，下面的p的while循环改成for循环可能更好理解
public void dfs(TreeNode root) {//用哈希表存储所有节点的父节点
if (root.left != null) {
parent.put(root.left.val, root);
dfs(root.left);
}
if (root.right != null) {
parent.put(root.right.val, root);
dfs(root.right);
}
}
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
dfs(root);
while (p != null) {
visited.add(p.val);//找到p节点后，记录回溯过程遇到的节点的值
p = parent.get(p.val);
}
while (q != null) {
if (visited.contains(q.val)) {//找到q节点后，回溯时如果和p节点遇到同样值，立即返回，此节点即为最深公共节点
return q;
}
q = parent.get(q.val);
}
return null;
}
}
网友答案：递归
分析：
若root是p,q的最近公共祖先，则有以下几种情况：
（1）p和q在root的子树中，且分列root的异侧
（2）p=root，且q在root的左或右子树中
（3）q=root，且p在root的左或右子树中
class Solution {
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
if(root == null || root == p || root == q) return root;
TreeNode left = lowestCommonAncestor(root.left, p, q);// 递归遍历左子树，只要在左子树中找到了p或q，则先找到谁就返回谁
TreeNode right = lowestCommonAncestor(root.right, p, q);// 递归遍历右子树，只要在右子树中找到了p或q，则先找到谁就返回谁
if(left == null) return right;//p,q都不在root的左子树，直接返回右子树，缩小范围
if(right == null) return left;//p,q都不在root的右子树，直接返回右子树
return root;//root的左右子树同时为空，证明p,q在root的异侧
//还有隐藏的一句
//if(left==null&&right==null) return null;
}
}