【数据结构_11】二叉树（3）

一、判断是否是完全二叉树

    //判断一棵树是不是完全二叉树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);}
}