一、 树的子结构:
1、题目:
输入两棵二叉树A,B,判断B是不是A的子结构。(ps:我们约定空树不是任意一个树的子结构。
2、解题思路:
这个题比较简单,利用递归的方式就可以判断B是不是A树的子结构。
3、实现代码:
public boolean HasSubtree(TreeNode root1,TreeNode root2) {
//当tree1和tree2都不为空的时候,才进行比较。否则直接返回false
if(root1 ==null || root2 == null){
return false;
}
以这个根节点为、根节点左子树、右子树 为起点判断是否包含Tree2
return (isSubtree(root1,root2) || HasSubtree(root1.left,root2) || HasSubtree(root1.right, root2));
}
private boolean isSubtree(TreeNode root1, TreeNode root2) {
//以下两个if的顺序不能调换
//如果tree2已经遍历完了,表示都可以对应上,返回true
if(root2==null)
return true;
//如果tree2已经遍历完,tree1还没遍历完,返回false
if(root1==null)
return false;
//如果根节点对应的上,那么就分别去子节点里面匹配
if(root1.val ==root2.val){
return (isSubtree(root1.left,root2.left) && isSubtree(root1.right, root2.right));
}else{
return false;
}
}
二、二叉树的镜像:
1、题目:
操作给定的二叉树,将其变换为源二叉树的镜像。
2、输入描述:
二叉树的镜像定义:源二叉树
8
/ \
6 10
/ \ / \
5 7 9 11
镜像二叉树
8
/ \
10 6
/ \ / \
11 9 7 5
3、解决思路:
采用递归的方式,递归交换每一个父节点的两个子节点的位置。
4、实现代码:
/**
public class TreeNode {
int val = 0;
TreeNode left = null;
TreeNode right = null;
public TreeNode(int val) {
this.val = val;
}
}
*/
public class Solution {
public void Mirror(TreeNode root) {
if(root==null)
return ;
if(root.left==null && root.right==null)
return;
TreeNode temp=root.left;
root.left=root.right;
root.right=temp;
Mirror(root.left);
Mirror(root.right);
}
}
三、二叉树的深度:
1、题目:
输入一棵二叉树,求该树的深度。从根结点到叶结点依次经过的结点(含根、叶结点)形成树的一条路径,最长路径的长度为树的深度。
2、解决思路:
递归方式和层序遍历方式都可以解决。
3、代码实现:
public class Test3 {
//第二种:非递归方式:层序遍历:
public int TreeDepth(TreeNode root) {
if(root == null){
return 0;
}
Queue<TreeNode> queue = new LinkedList<TreeNode>();
queue.add(root);
//depth代表当前节点所在的层数,count代表已经遍历的节点数,nextCount代表下一层的节点数
//当count==nextCount的时候,代表本次节点已经遍历完毕
int depth=0,count=0,nextCount=1;
while(queue.size()!=0){
count++;
TreeNode top = queue.poll();
if(top.left!=null){
queue.add(top.left);
}
if(top.right!=null){
queue.add(top.right);
}
if(count==nextCount){
depth++;
count=0;
nextCount=queue.size();
}
}
return depth;
}
//第一种:递归方式
public int TreeDepth1(TreeNode root) {
if(root == null){
return 0;
}
int left= TreeDepth1(root.left);
int right =TreeDepth1(root.right);
return Math.max(left, right)+1;
}
}
class TreeNode {
int val = 0;
TreeNode left = null;
TreeNode right = null;
public TreeNode(int val) {
this.val = val;
}
}
四、平衡二叉树:
1、题目:
输入一棵二叉树,判断该二叉树是否是平衡二叉树。
2、解题思路:
递归方式或者后序遍历的方式都可以解决。
3、代码实现:
public class Test5 {
private boolean isBalanced = true;
//第三种:后续遍历时,遍历到一个节点,其左右子树已经遍历 依次自底向上判断,每个节点只需要遍历一次
public boolean IsBalanced_Solution2(TreeNode root) {
getDepth2(root);
return isBalanced;
}
public int getDepth2(TreeNode root){
if(root == null){
return 0;
}
int left=getDepth2(root.left);
int right=getDepth2(root.right);
if(Math.abs(left-right)>1){
isBalanced=false;
}
return Math.max(left, right)+1;
}
//第二种方法:三种中最好的方式
//如果改为从下往上遍历,如果子树是平衡二叉树,则返回子树的高度;如果发现子树不是平衡二叉树,
//则直接停止遍历,这样至多只对每个结点访问一次。
public boolean IsBalanced_Solution1(TreeNode root) {
return getDepth(root) !=-1;
}
public int getDepth(TreeNode root){
if(root == null) return 0;
int left=getDepth(root.left);
if(left == -1 ) return -1;
int right=getDepth(root.right);
if(right == -1) return -1;
return Math.abs(left-right)>1?-1:1+Math.max(left, right);
}
//第一种方法:递归方式
//这种做法有很明显的问题,在判断上层结点的时候,会多次重复遍历下层结点,增加了不必要的开销。
public boolean IsBalanced_Solution(TreeNode root) {
if(root == null){
return true;
}
return Math.abs(maxDepth(root.left)-maxDepth(root.right))<=1
&& IsBalanced_Solution(root.left) && IsBalanced_Solution(root.right);
}
private int maxDepth(TreeNode root){
if(root == null){
return 0;
}
return 1+Math.max(maxDepth(root.left), maxDepth(root.right));
}
}
class TreeNode {
int val = 0;
TreeNode left = null;
TreeNode right = null;
public TreeNode(int val) {
this.val = val;
}
}
发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/114698.html原文链接:https://javaforall.cn
【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛
【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...