二叉树的基本操作（二）

• 检测值为 value 的值是否存在

    public TreeNode find(TreeNode root, int val){
//        1、判断根节点是否为空
       if(root == null){
           return null;
       }
//       2.判断是否为根节点
       if(root.val == val){
           return root;
       }
//       3.判断左子树
       TreeNode ret1 = find(root.left,val);
       if(ret1 != null){
           return ret1;
       }
//       4.判断右子树
       TreeNode ret2 = find(root.right,val);
       if(ret2 != null){
           return ret2;
       }
//       5。左右子树都没有则返回空
       return null;
    }

• 判断两颗二叉树是否相同
• 时间复杂度 O(min(m,n)) ,m 和 n分别为两棵二叉树的节点的个数

//    判断两棵二叉树是否相同
    public boolean isSameTree(TreeNode p,TreeNode q){
//        1. 一颗树为空，一颗不为空，返回false
        if(p==null&&q != null || p != null && q == null){
            return false;
        }
//        2. 如果两颗都为空，则返回true
        if(p == null && q == null){
            return true;
        }
//        3.如果val值不相同，则两棵树不相同
        if(p.val != q.val){
            return false;
        }
//        左右子树都相同,则两棵树相同
        return isSameTree(p.left,q.left) && isSameTree(p.right,q.right);
    }

• 判断二叉树是否为另一棵树的子树
• 时间复杂度 : O（ｒ＊ｓ）　ｒ为root的节点个数，ｓ为ｓｕｂｒｏｏｔ的节点个数

 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;
//       3.判断是否为右子树
        if(isSubtree(root.right,subRoot)) return true;
        return false;
    }
   public boolean isSameTree(TreeNode p,TreeNode q){
//        1. 一颗树为空，一颗不为空，返回false
        if(p==null&&q != null || p != null && q == null){
            return false;
        }
//        2. 如果两颗都为空，则返回true
        if(p == null && q == null){
            return true;
        }
//        3.如果val值不相同，则两棵树不相同
        if(p.val != q.val){
            return false;
        }
//        左右子树都相同,则两棵树相同
        return isSameTree(p.left,q.left) && isSameTree(p.right,q.right);
    }

• 反转二叉树

反转二叉树即反转二叉树的左树和右树，首先将根节点的左树与右树节点进行反转，然后再递归反转根节点的左节点和右节点 , 即root .left为根的左右节点 和以root.right为根的左右节点 ，以此类推

class Solution {
    public TreeNode invertTree(TreeNode root) {
        if(root == null){
            return null;
        }
        TreeNode tmp = root.right;
        root.right = root.left;
        root.left = tmp;
        invertTree(root.left);
        invertTree(root.right);
        return root;
    }
}

• 判断是否为对称二叉树

 public boolean isSymmetric(TreeNode root) {
//        根节点为空时，默认为对称
          if(root  == null){
              return true;
          }
//          判断根节点的左子树和右子树
          return isSysmmertricChild(root.left,root.right);
    }
    private boolean isSysmmertricChild(TreeNode leftTree ,TreeNode rightTree){
//        如果左子树为空右子树不为空或者左子树不为空右子树为空
        if(leftTree != null && rightTree == null || leftTree == null && rightTree != null){
            return false;
        }
        if(leftTree == null && rightTree == null){
            return true;
        }
        if(leftTree.val != rightTree.val){
            return true;
        }
        return isSysmmertricChild(leftTree.left,rightTree.right)&&isSysmmertricChild(leftTree.right,rightTree.left);
    }

• 二叉树的层序遍历

 public void levelOrder(TreeNode root) {
          if(root == null){
              return;
          }
        Queue<TreeNode> qu = new LinkedList<>();
        qu.offer(root);
        while(!qu.isEmpty()){
            TreeNode cur = qu.poll();
            System.out.println(cur.val+" ");
            if(cur.left != null){
                qu.offer(cur.left);
            }
            if(cur.right != null){
                qu.offer(cur.right);
            }

        }

• 二叉树的遍历

编一个程序，读入用户输入的一串先序遍历字符串，根据此字符串建立一个二叉树（以指针方式存储）。 例如如下的先序遍历字符串： ABC##DE#G##F### 其中“#”表示的是空格，空格字符代表空树。建立起此二叉树以后，再对二叉树进行中序遍历，输出遍历结果。

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 void main(String[] args) {
        Scanner in = new Scanner(System.in);
        // 注意 hasNext 和 hasNextLine 的区别
        while (in.hasNextLine()) { // 注意 while 处理多个 case
           String str = in.nextLine();
           TreeNode root = buildTree(str);
           inOrder(root);
        }
    }
  private static int i = 0;
  private static TreeNode buildTree(String str){
      TreeNode root = null;
      if(str.charAt(i)!='#'){
         root = new TreeNode(str.charAt(i));
         i++;
         root.left = buildTree(str);
         root.right = buildTree(str);
      }else{
          i++;
      }
     return root;
  }
   private static void inOrder(TreeNode root){
       if(root  == null){
           return;
       }
       inOrder(root.left);
       System.out.print(root.val+" ");
       inOrder(root.right);
   }
}

• 判断是否为完全二叉树

将二叉树的所有节点按照层序遍历的方法放入队列中，如果二叉树为完全二叉树，那么队列中的元素出队时，过程中的节点不为空，遇到空节点时，剩下的节点一定都为空，反之，如果不为完全二叉树，剩下的元素出队时一定会存在非null的值

 public boolean isCompleteTree (TreeNode root) {
      if(root == null){
        return false;
      }
    Queue<TreeNode> qu = new LinkedList<>();
    qu.offer(root);
     while(!qu.isEmpty()) {
       TreeNode cur = qu.poll();
         if(cur != null){
          qu.offer(cur.left);
          qu.offer(cur.right);
         }else{
            break;
         }
     }
      while(!qu.isEmpty()){
        TreeNode cur2 = qu.poll();
        if(cur2 != null){
          return false;
        }
      }
      return true;
    }