做基金哪个网站好/网站收录情况查询
一、判断是否是完全二叉树
//判断一棵树是不是完全二叉树public static Boolean isComplete(Node root){//首先判断是否为空树 如果是空树，我们认为它是完全二叉树if(root == null){return true;}//开始访问这棵树//创建一个队列，把树上的元素进行层序遍历Queue<Node> queue = new LinkedList<>();queue.offer(root);//创建一个标志，用于区分一阶段和二阶段Boolean isFirstPhase = true;while(!queue.isEmpty()){Node cur = queue.poll();if(isFirstPhase){//1.如果没有子树，进入二阶段if(cur.left == null && cur.right == null){isFirstPhase =false;}else if( cur.left != null && cur.right == null){//2.如果只有左子树，也进入二阶段isFirstPhase =false;//并且还要将左子树的元素放入队列中queue.offer(cur.left);}else if(cur.right!= null && cur.left == null){//3.如果只有右子树 那就返回falsereturn false;}else if(cur.left != null &&cur.right != null){//如果左右子树都不为空 就继续进行遍历操作queue.offer(cur.left);queue.offer(cur.right);}}else{//开始处理二阶段//在二阶段中，我们需要让所有子树为空，否则就返回falseif( cur.left != null || cur.right != null){return false;}}}//循环出来可知，这棵树没有能让我们在概念上挑出错误的地方 所以return truereturn true;}思路：
对树进行层序遍历
1.要求每个节点必须有两个子树
(a)没有子树，进入二阶段
(b)只有左子树，进入二阶段
(c)只有右子树，判定为false
2.要求每个节点必须没有子树
二、判断是否是相同的树
思路：
1.判定两个树的根节点的值，是否相同
2.递归判定左子树是否相同
3.递归判定右子树是否相同
只要发现上面任何一个环节出现不同，就认为是false
当所有的递归完成后，也没有找到不同的地方，就是true
//1.首先判断两棵树是否为空树if(p == null && q == null){return true;}if(( p == null && q != null) ||(p != null && q == null)){return false;}//判断两个节点的值是否相同if( p.val != q.val){return false;}Boolean leftIsSameTree = isSameTree(p.left,q.left);Boolean rightIsSameTree = isSameTree(p.right,q.right);return leftIsSameTree && rightIsSameTree;三、是否是另一颗树的子树
思路：首先还是按照递归的思路来进行处理，给定一个root和一个subRoot
1.检查root 和subRoot是不是相同（题目的要求，相同，也是合法的包含关系）
2.如果是不相同，递归的判定，root.left是否包含subRoot；递归的判定，root.right是否包含subRoot。
/*** 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) {//1.首先判断两棵树是否为空树if(p == null && q == null){return true;}if(( p == null && q != null) ||(p != null && q == null)){return false;}//判断两个节点的值是否相同if( p.val != q.val){return false;}Boolean leftIsSameTree = isSameTree(p.left,q.left);Boolean rightIsSameTree = isSameTree(p.right,q.right);return leftIsSameTree && rightIsSameTree;}public boolean isSubtree(TreeNode root, TreeNode subRoot) {if(root == null && subRoot == null){return true;}if(root == null && subRoot != null){return false;}if(root != null && subRoot == null){return true;}if(isSameTree(root,subRoot)){return true;}return isSubTree(root.left,subRoot) || isSubTree(root.right,subRoot);}
}四、翻转二叉树
思路：针对这个二叉树，进行遍历，访问节点操作，就是“交换两个子树”
/*** 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;}invertTree(root.left);invertTree(root.right);TreeNode tmp = root.left;root.left = root.right;root.right = tmp;return root;}
}五、判定是否是平衡二叉树
平衡二叉树的概念：
思路：针对树进行遍历（先序中序层序......）针对每个节点，都计算左右子树的高度，算出高度之后计算高度差值是否<=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 static int getHeight(TreeNode root){if(root == null){return 0;}return 1+(Math.max(getHeight(root.left),getHeight(root.right)));}public boolean isBalanced(TreeNode root) {if(root == null){return true;}if(root.right == null && root.left == null){return true;}int leftHeight = getHeight(root.left);int rightHetght = getHeight(root.right);if(leftHeight - rightHetght > 1 ||rightHetght - leftHeight >1){return false;}return isBalanced(root.right)&&isBalanced(root.left);}
}六、对称二叉树
思路：判定树是否为轴对称，就相当于判定这个树的左右子树，是否互为镜像。
递归地完成判定两个树是否是镜像。
1.根节点的值是否相同
值不相同，直接返回false
2.判定t1.left 和t2.right是否互为镜像
3.判定t1.right和t2.left是否互为镜像
/*** 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 static Boolean isMorror(TreeNode p,TreeNode q){//首先判别几种特殊的情况if(p == null && q== null){return true;}if((p == null && q != null) ||(p != null && q == null)){return false;}if(p.val != q.val){return false;}Boolean Mirror1 = isMorror(p.left ,q.right);Boolean Mirror2 = isMorror(p.right ,q.left);return Mirror1 && Mirror2;}public boolean isSymmetric(TreeNode root) {if(root == null){return true;}return isMorror(root.right,root.left);}
}七、二叉树的构建
思路：取出这里的节点的过程中，下一个节点，就是当前节点左子树的根节点，如果遇到了#，再下一个节点，就是当前节点右子树的根节点，如果树根，左、右，都构建过了，就往上层返回，看上层的右子树是否构建了。上述过程也是先序遍历的递归，此处递归的访问操作是“构建节点”。
import java.util.Scanner;// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {static class Node {public char val;Node left = null;Node right = null;public Node(char val) {this.val = val;}}public static void main(String[] args) {Scanner in = new Scanner(System.in);// 注意 hasNext 和 hasNextLine 的区别// 每次循环, 都在处理一个用例.while (in.hasNextLine()) { // 注意 while 处理多个 caseString line = in.nextLine();// 要输入的内容了.// 1. 构建出二叉树. 确保每次进行构建之前, index 都置为 0. 避免多个用例相互影响的情况.index = 0;Node root = build(line);// 2. 中序遍历打印二叉树的节点inOrder(root);// 整个中序遍历完成后, 再加上换行. 题目要求每个输出的结果占一行.System.out.println();}}// 由于这里的 build 需要进行递归的~~// 意味着如果在这个方法内部创建 int index 局部变量, 这个变量的值就会在递归过程中, 创建出新的.// 需要让所有的递归过程都是针对同一个 index 修改.// 此处就把 index 创建为成员变量.private static int index = 0;public static Node build(String s) {// 取出 index 位置的字符.char c = s.charAt(index);if (c == '#' || c == ' ') {// 题目的描述不清楚, 所以就需要把两种情况都考虑一下.return null;}// 不为空, 把这个 c 构建成 Node// root 就是当前子树的根节点.Node root = new Node(c);// 先 index++ 一下, 准备取下一个节点.// 根据下一个节点, 递归构建 root 的左子树.index++;root.left = build(s);// 再次 index++ 一下, 准备取下一个节点.// 根据下一个节点, 递归的构建 root 的右子树.index++;root.right = build(s);return root;}public static void inOrder(Node root) {if (root == null) {return;}inOrder(root.left);System.out.print(root.val + " ");inOrder(root.right);}
}