226. 翻转二叉树
给你一棵二叉树的根节点 root ，翻转这棵二叉树，并返回其根节点。
输入：root = [4,2,7,1,3,6,9]
输出：[4,7,2,9,6,3,1]
ψ(｀∇´)ψ 我的思路
- 还是用了层序遍历的方法，在该结点左右孩子入栈之后，互换左右指针
/**
* 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) {
Queue<TreeNode> que = new LinkedList<>();
if (root == null) {
return root;
}
que.add(root);
while (!que.isEmpty()) {
int size = que.size();
while (size > 0) {
TreeNode node = que.poll();
TreeNode tmp = new TreeNode();
if (node.right != null && node.left != null) {
//左右孩子都不空，右孩子、左孩子加入队列并交换
que.add(node.right);
que.add(node.left);
tmp = node.right;
node.right = node.left;
node.left = tmp;
} else if (node.right==null&&node.left!=null ) {
que.add(node.left);
node.right=node.left;
node.left=null;
} else if(node.left==null&&node.right!=null){
que.add(node.right);
node.left=node.right;
node.right=null;
}
size--;
}
}
return 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 TreeNode invertTree(TreeNode root) {
if (root == null) {
return null;
}
//先序遍历
swapChildren(root);
invertTree(root.left);
invertTree(root.right);
return root;
}
private void swapChildren(TreeNode root) {
TreeNode tmp = root.left;
root.left = root.right;
root.right = tmp;
}
}
101. 对称二叉树
给你一个二叉树的根节点 root ， 检查它是否轴对称。
输入：root = [1,2,2,3,4,4,3]
输出：true
ψ(｀∇´)ψ 我的思路
- 层序遍历每一层二叉树，每一层结点的值放入链表，判断链表（除第一层外）是否对称
/**
* 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 boolean isSymmetric(TreeNode root) {
Queue<TreeNode> que = new LinkedList<>();
que.add(root);
while (!que.isEmpty()){
int size = que.size();
List<Integer> list = new ArrayList<>();
while (size>0){
TreeNode node = que.poll();
list.add(node.val);//加入链表
if(node.left!=null){que.add(node.left);}
if(node.right!=null){que.add(node.right);}
size--;
}
//判断list是不是对称列表
if(list.size()>1){
Collections.reverse(list.subList(0,list.size()/2));
if(!list.subList(0,list.size()/2).equals(list.subList(list.size()/2,list.size()))){
return false;
}
}
}
return true;
}
}
-
上面的代码并不能判断下面这种情况：
输入：root = [1,2,2,null,3,null,3]
输出：false -
因为只把不空的结点加入到链表，所以上述情况的链表是这样的：[1][2,2][3,3],我想着把null也加入到链表里。不行(x_x)，那样的话就没办法控制临界条件了。
-
下面是代码随想录的递归做法：比较根结点的左右子树是否对称
/**
* 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 boolean isSymmetric(TreeNode root) {
boolean res = comparable(root.left, root.right);
return res;
}
public static boolean comparable(TreeNode left, TreeNode right){
if(left==null&&right!=null){return false;}
else if(right==null&&left!=null){return false;}
else if(right==null&&left==null){return true;}
else if(right.val!= left.val){return false;}
boolean a = comparable(left.left, right.right);//比较外侧结点
boolean b = comparable(left.right, right.left);//比较内测结点
boolean res = a && b;
return res;
}
}
- 感觉递归的做法要好理解很多，再写两道类似的题目练一下递归
100. 相同的树
给你两棵二叉树的根节点 p 和 q ，编写一个函数来检验这两棵树是否相同。
如果两个树在结构上相同，并且节点具有相同的值，则认为它们是相同的。
/**
* 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 boolean isSameTree(TreeNode p, TreeNode q) {
//if(p==null&&q==null){return false;}
return comparable(p,q);
}
public boolean comparable(TreeNode p,TreeNode q){
if(p!=null&&q==null){return false;}
else if(p==null&&q==null){return true;}
else if(p==null&&q!=null){return false;}
else if(p.val!=q.val){return false;}
boolean a = comparable(p.left,q.left);
boolean b = comparable(p.right,q.right);
return a && b;
}
}
572. 另一棵树的子树
给你两棵二叉树 root 和 subRoot 。检验 root 中是否包含和 subRoot 具有相同结构和节点值的子树。如果存在，返回 true ；否则，返回 false 。
二叉树 tree 的一棵子树包括 tree 的某个节点和这个节点的所有后代节点。tree 也可以看做它自身的一棵子树。
/**
* 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 boolean isSubtree(TreeNode root, TreeNode subRoot) {
//前序遍历root
List<TreeNode> nodes = new ArrayList<>();
preorder(root,nodes);
for (TreeNode node : nodes) {
//此时nodes里面是root中的所有结点
if(comparable(node, subRoot)){
return true;
}
}
return false;
}
public void preorder(TreeNode root, List<TreeNode> nodes){
if(root==null){return ;}
nodes.add(root);
preorder(root.left,nodes);
preorder(root.right,nodes);
}
public boolean comparable(TreeNode left,TreeNode right){
if(left==null&&right==null){return true;}
else if(left!=null&&right==null){return false;}
else if(left==null&&right!=null){return false;}
else if(left.val!= right.val){return false;}
boolean a = comparable(left.left, right.left);
boolean b = comparable(left.right, right.right);
return a && b;
}
}
104. 二叉树的最大深度
- 这题昨天用层序遍历写过，下面是递归的实现：
/**
* 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 maxDepth(TreeNode root) {
//这里用根结点的高度表示二叉树的最大深度
if(root==null){return 0;}
int leftDepth = maxDepth(root.left);//左孩子的高度
int rightDepth = maxDepth(root.right);//右孩子的高度
return Math.max(leftDepth,rightDepth)+1;//当前结点的高度（左孩子的高度，右孩子的高度的最大值+1）
//后序遍历
}
}
- 感觉递归还是不太好理解
559. N 叉树的最大深度
给定一个 N 叉树，找到其最大深度。
最大深度是指从根节点到最远叶子节点的最长路径上的节点总数。
N 叉树输入按层序遍历序列化表示，每组子节点由空值分隔
/*
// Definition for a Node.
class Node {
public int val;
public List<Node> children;
public Node() {}
public Node(int _val) {
val = _val;
}
public Node(int _val, List<Node> _children) {
val = _val;
children = _children;
}
};
*/
class Solution {
public int maxDepth(Node root) {
if(root==null){return 0;}
List<Node> children = root.children;//当前结点的孩子们
int max = 0;
for (Node child : children) {
int depth = maxDepth(child);
max = Math.max(depth,max);
}
return max+1;
}
}
- 扩展成n叉树，和二叉树区别不大，就是孩子数不确定，用for循环遍历求孩子的高度就好
111. 二叉树的最小深度
给定一个二叉树，找出其最小深度。
最小深度是从根节点到最近叶子节点的最短路径上的节点数量。
说明：叶子节点是指没有子节点的节点。
ψ(｀∇´)ψ 我的思路
- 稍微改了二叉树最大深度的代码，
/**
* 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 minDepth(TreeNode root) {
if(root==null){return 0;}//空的结点是第0层(也是递归出口)
int leftDepth = minDepth(root.left);
int rightDepth = minDepth(root.right);
return Math.min(leftDepth,rightDepth)+1;
}
}
- 代码在运行下图例子时返回1
题目中说的是：最小深度是从根节点到最近叶子节点的最短路径上的节点数量。
- 在上述代码中，只有一个孩子的结点会被误以为是叶子结点，返回该结点的高度。改进后代码如下：
/**
* 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 minDepth(TreeNode root) {
if(root==null){return 0;}//空的结点是第0层(也是递归出口)
int leftDepth = minDepth(root.left);
int rightDepth = minDepth(root.right);
if(root.left==null){return rightDepth+1;}//如果左子树为空，返回右子树的高度+1
else if(root.right==null){return leftDepth+1;}//如果右子树为空，返回左子树的高度+1
return Math.min(leftDepth,rightDepth)+1;
}
}
222. 完全二叉树的节点个数
完全二叉树 的根节点 root ，求出该树的节点个数。
完全二叉树 的定义如下：在完全二叉树中，除了最底层节点可能没填满外，其余每层节点数都达到最大值，并且最下面一层的节点都集中在该层最左边的若干位置。若最底层为第 h 层，则该层包含 1~ 2h 个节点。
ψ(｀∇´)ψ 我的思路
- 层序遍历，每弹出一个数count++
/**
* 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 countNodes(TreeNode root) {
Queue<TreeNode> que = new LinkedList<>();
if(root==null){return 0;}
int count = 0;
que.add(root);
while (!que.isEmpty()){
int size = que.size();
while (size>0){
count++;
TreeNode node = que.poll();
if(node.left!=null){que.add(node.left);}
if(node.right!=null){que.add(node.right);}
size--;
}
}
return count;
}
}