西安网站建设报价,深圳网站快速排名优化,凌云网站,深圳建设局和住建局博主主页: 码农派大星.
关注博主带你了解更多数据结构知识 1判断相同的树 OJ链接 这道题相对简单,运用我们常规的递归写法就能轻松写出
所以我们解题思路应该这样想:
1.如果p为空#xff0c;q为空#xff0c;那么就是两颗空树肯定相等 2.如果一个树为空另一棵树不为空那么…
博主主页: 码农派大星.
关注博主带你了解更多数据结构知识 1判断相同的树 OJ链接 这道题相对简单,运用我们常规的递归写法就能轻松写出
所以我们解题思路应该这样想:
1.如果p为空q为空那么就是两颗空树肯定相等 2.如果一个树为空另一棵树不为空那么一定不相等 3.如果都不为空值相同才相等。 4.再递归判断左子树是否相等右子树是否相等只有左右子树都相等才是相同的树
class Solution {public boolean isSameTree(TreeNode p, TreeNode q) {//1,一个为空一个不为空if(p ! null q null || p null q ! null){return false;}//2,第一步走完要么都为空 要么都不为空 两个都是空if(p null q null){return true;}//3,都不为空if(p.val ! q.val){return false;}//4,此时代表两个都不为空,同时val也是一样//5,说明根节点相同,接下来判断两棵树的左 右是不是同时相同return isSameTree(p.left,q.left) isSameTree(p.right,q.right);}
}
2判断另一课树的子树OJ链接
给你两棵二叉树 root 和 subRoot 。检验 root 中是否包含和 subRoot 具有相同结构和节点值的子树。如果存在返回 true 否则返回 false 。 这道题也要用到我们的递归思想
1如果都为空树,则false
2如果俩个树为相同的树,则true
3 再递归看sub是否为左子树的子树右子树的子树如果都不是则返回false
class Solution {public boolean isSubtree(TreeNode root, TreeNode subRoot) {if(root null){return false;}//1,判断两个树是不是相同的树if(isSameTree(root,subRoot)){return true;}//2,if(isSubtree(root.left,subRoot)){return true;}if(isSubtree(root.right,subRoot)){return true;}return false; }public boolean isSameTree(TreeNode p, TreeNode q) {//1,一个为空一个不为空if(p ! null q null || p null q ! null){return false;}//2,第一步走完要么都为空 要么都不为空 两个都是空if(p null q null){return true;}//3,都不为空if(p.val ! q.val){return false;}//4,此时代表两个都不为空,同时val也是一样//5,说明根节点相同,接下来判断两棵树的左 右是不是同时相同return isSameTree(p.left,q.left) isSameTree(p.right,q.right);}} 3翻转二叉树OJ链接 同样的递归思想,不变的套路
1判断是否为空树
2再用递归交换左右树
class Solution {public TreeNode invertTree(TreeNode root) {if(root null){return null;}TreeNode tmp root.left;root.left root.right;root.right tmp;invertTree(root.left);invertTree(root.right);return root;}
}
4平衡二叉树OJ链接 1判断是否空树
2求左树的深度和右树的深度
3判断左树的深度减右树的深度不能大于1
左树和右数的子树也一样
math.abs() 是一个数学函数它用于返回一个数的绝对值
class Solution {public boolean isBalanced(TreeNode root) {if(root null){return true;}return getHeight(root) 1;}//获取二叉树高度public int getHeight(TreeNode root){if(root null){return 0;}int leftHeight getHeight(root.left);if(leftHeight 0){return -1;}int rightHeight getHeight(root.right);if(rightHeight 0){return -1;}if(Math.abs(leftHeight - rightHeight) 1){return Math.max(leftHeight,rightHeight) 1;}else{return -1;}}
}
5对称二叉树 OJ链接 1判断是否根节点为空
2 检查结构是否相同:一个为空一个不为空
3检查结构:两个都为空或两个都不为空
4判断左右根节点是否相同
5开始判断是否对称 递归开始:
满足左子树的左 和 右子树的右 对称 同时 左子树的右 和 右子树的左 对称
class Solution {public boolean isSymmetric(TreeNode root) {if(root null) return true;return isSymmetricChild(root.left,root.right);}public boolean isSymmetricChild(TreeNode leftTree,TreeNode rightTree){//1检查结构是否相同---一个为空一个不为空if(leftTree ! null rightTree null || leftTree null rightTree !null){return false;}//2检查结构---两个都为空或两个都不为空if(leftTree null rightTree null){return true;}//3检查结狗---- 处理两个都为空或两个都不为空if(leftTree.val ! rightTree.val){return false;}//4.此时两个引用都不为空而且节点值一样//5开始判断是否对称//6满足左子树的左 和 右子树的右 对称 同时 左子树的右 和 右子树的左 对称return isSymmetricChild(leftTree.left,rightTree.right) isSymmetricChild(leftTree.right,rightTree.left);}
} 6二叉树的层序遍历OJ链接 我们需要借助队列来实现:
1判空
2 将root入队列,出队时在让root.left(cur.left)和root.right(cur.right)入队
循环这样的操作,知道队列为空
class Solution {public ListListInteger levelOrder(TreeNode root) {ListListInteger ret new ArrayList();if(root null){return ret;}QueueTreeNode queue new LinkedList();queue.offer(root);while (!queue.isEmpty()){int size queue.size();ListInteger list new ArrayList();while (size 0){TreeNode cur queue.poll();list.add(cur.val);if(cur.left ! null){queue.offer(cur.left);}if(cur.right ! null){queue.offer(cur.right);}size--;}ret.add(list);}return ret;}
}
7二叉树的遍历OJ链接
读入用户输入的一串先序遍历字符串根据此字符串建立一个二叉树以指针方式存储。 例如如下的先序遍历字符串 ABC##DE#G##F### 其中“#”表示的是空格空格字符代表空树。建立起此二叉树以后再对二叉树进行中序遍历输出遍历结果。 1遍历字符串 跳过#,其他的字符串都new为新Node,此时字符串就是先序遍历的状态
2遍历字符串的时候我们要把i设置为成员变量防止每次递归后i从0开始
3.遍历二叉树中序输出
import java.util.Scanner;
class TreeNode{public char val;public TreeNode left;public TreeNode right;public TreeNode(char val){this.val val;}
}
public class Main {public static int i 0;public static TreeNode createTree(String str){TreeNode root null;if(str.charAt(i) ! #){root new TreeNode(str.charAt(i));i;root.left createTree(str);root.right createTree(str);}else{i;}return root;}public static void inorder(TreeNode root){if(root null){return;}inorder(root.left);System.out.print(root.val );inorder(root.right);}public static void main(String[] args) {Scanner in new Scanner(System.in);// 注意 hasNext 和 hasNextLine 的区别while (in.hasNextLine()) { // 注意 while 处理多个 caseString str in.nextLine();TreeNode root createTree(str);inorder(root);}}
}
