这些问题都有一个类TreeNode。
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;
}
}
一.相同的树
给你两棵二叉树的根节点 p 和 q ，编写一个函数来检验这两棵树是否相同。(如果两个树在结构上相同，并且节点具有相同的值，则认为它们是相同的)
思路
采用递归思路，也是深度优先搜索，具体看代码解释便可以懂。
代码
public boolean isSameTree(TreeNode p, TreeNode q) {
//p，q同时为空节点
if(p==null&&q==null){
return true;
}
//其中p，q有一个为空一个不为空(那么必然不相等)
if(p==null||q==null){
return false;
}
//其中有节点的val不相等，那么也就不相等了
if(p.val!=q.val){
return false;
}
return isSameTree(p.left,q.left)&&isSameTree(p.right,q.right);
}
二.另一棵树的子树
给你两棵二叉树 root 和 subRoot 。检验 root 中是否包含和 subRoot 具有相同结构和节点值的子树。如果存在，返回 true ；否则，返回 false 。
二叉树 tree 的一棵子树包括 tree 的某个节点和这个节点的所有后代节点。tree 也可以看做它自身的一棵子树。
思路
深度优先暴力解法，需要用到相同的树这个题的代码。
代码
public boolean isSubtree(TreeNode root, TreeNode subRoot) {
//都是空树，则条件一定成立
if (root==null&&subRoot==null){
return true;
}
//一个为空一个不为空，那么就不构成子树条件
if(root==null||subRoot==null){
return false;
}
//设置ret变量，存放判断是否是相同的树
boolean ret=false;
if(root.val==subRoot.val){
ret=isSameTree(root,subRoot);
}
//左右递归，只要出现一个子树，那么就条件成立
return ret||isSubtree(root.left,subRoot)||isSubtree(root.right,subRoot);
}
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);
}
三.二叉树的最大深度
给定一个二叉树，找出其最大深度。
二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。（说明: 叶子节点是指没有子节点的节点）
思路
依然深度优先搜索，递归遍历，（代码简洁明了，可读性高）
代码
public int maxDepth(TreeNode root) {
//空树着，则为0
if(root==null){
return 0;
}
//当左右都为空的时候，那么就是叶子节点了，返回1
if(root.left==null&&root.right==null){
return 1;
}
//递归记录，左右子树的深度
int left=maxDepth(root.left);
int right=maxDepth(root.right);
//三目运算，保留最大的深度
return 1+(left>right?left:right);
}
四.平衡二叉树
给定一个二叉树，判断它是否是高度平衡的二叉树。
本题中，一棵高度平衡二叉树定义为：一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1 。
思路
自顶向下的深度优先搜索，递归遍历。需要用到***二叉树的最大深度***的代码
代码
public boolean isBalanced(TreeNode root) {
//空树，一定符合平衡条件
if(root==null){
return true;
}
//只有一个根节点，左右子树都为空，也符合平衡条件
if(root.left==null&&root.right==null){
return true;
}
//利用求二叉树的最大深度的代码，求出最大深度
int left=maxDepth(root.left);
int right=maxDepth(root.right);
//出现左右高度差超过1,那么就一定不符合平衡条件了
if(left-right>1||left-right<-1){
return false;
}
//深度优先遍历
return isBalanced(root.left)&&isBalanced(root.right);
}
public int maxDepth(TreeNode root) {
if(root==null){
return 0;
}
if(root.left==null&&root.right==null){
return 1;
}
int left=maxDepth(root.left);
int right=maxDepth(root.right);
return 1+(left>right?left:right);
}
五.对称二叉树
- 对称二叉树
给定一个二叉树，检查它是否是镜像对称的。
思路
递归遍历，深度优先搜索，看代码中的解释即可。
代码
public boolean isSymmetric(TreeNode root) {
if(root==null){
return true;
}
return isMirror(root.left,root.right);
}
public boolean isMirror(TreeNode A,TreeNode B){
//空树，则符合对称
if(A==null&&B==null){
return true;
}
//其中一个为空，一个不为空，则一定不满足条件
if(A==null||B==null){
return false;
}
//对应位置值不相等，则也一定不满足条件
if(A.val!=B.val){
return false;
}
return isMirror(A.left,B.right)&&isMirror(A.right,B.left);
}
递归这个思想，我们切记一定不能纵向思考（去寻找递归的结果），要横向思考（寻找递归的公式），这才是这个思想的精髓。