java 数据结构二叉树-java判断满二叉树算法

  二叉堆 == 完全二叉树
  二叉堆满足二个特性：
  1．父结点的键值总是大于或等于（小于或等于）任何一个子节点的键值。
  2．每个结点的左子树和右子树都是一个二叉堆（都是最大堆或最小堆）。
  当父结点的键值总是大于或等于任何一个子节点的键值时为最大堆。当父结点的键值总是小于或等于任何一个子节点的键值时为最小堆。下图展示一个最小堆：
  
  堆的存储
  一般都用数组来表示堆，i结点的父结点下标就为(i – 1) / 2。它的左右子结点下标分别为2 i + 1和2 i + 2。如第0个结点左右子结点下标分别为1和2。
  
  二叉树的数据结构：
   class TreeNode{

     int val;
     //左孩子
     TreeNode left;
     //右孩子
     TreeNode right;
    }

  二叉树的题目普遍可以用递归和迭代的方式来解
  1. 求二叉树的最大深度
   int maxDeath(TreeNode node){

     if(node==null){
     return 0;
     }
     int left = maxDeath(node.left);
     int right = maxDeath(node.right);
     return Math.max(left,right) + 1;
    }

  2. 求二叉树的最小深度
   int getMinDepth(TreeNode root){

     if(root == null){
     return 0;
     }
     return getMin(root);
    }
    int getMin(TreeNode root){
     if(root == null){
     return Integer.MAX_VALUE;
     }
     if(root.left == null&&root.right == null){
     return 1;
     }
     return Math.min(getMin(root.left),getMin(root.right)) + 1;
    }

  3. 求二叉树中节点的个数
   int numOfTreeNode(TreeNode root){

     if(root == null){
     return 0;
     }
     int left = numOfTreeNode(root.left);
     int right = numOfTreeNode(root.right);
     return left + right + 1;
    }

  4. 求二叉树中叶子节点的个数
   int numsOfNoChildNode(TreeNode root){

     if(root == null){
     return 0;
     }
     if(root.left==null&&root.right==null){
     return 1;
     }
     return numsOfNodeTreeNode(root.left)+numsOfNodeTreeNode(root.right);
    }

  5. 求二叉树中第k层节点的个数
   int numsOfkLevelTreeNode(TreeNode root,int k){

     if(root == null||k1){
     return -1;
     }
     return Math.max(left, right) + 1;
    }

  7.判断二叉树是否是完全二叉树
   boolean isCompleteTreeNode(TreeNode root){

     if(root == null){
     return false;
     }
     Queue queue = new LinkedList();
     queue.add(root);
     boolean result = true;
     boolean hasNoChild = false;
     while(!queue.isEmpty()){
     TreeNode current = queue.remove();
     if(hasNoChild){
     if(current.left!=null||current.right!=null){
     result = false;
     break;
     }
     }else{
     if(current.left!=null&&current.right!=null){
     queue.add(current.left);
     queue.add(current.right);
     }else if(current.left!=null&&current.right==null){
     queue.add(current.left);
     hasNoChild = true;
     }else if(current.left==null&&current.right!=null){
     result = false;
     break;
     }else{
     hasNoChild = true;
     }
     }
     }
     return result;
    }

  8. 两个二叉树是否完全相同
   boolean isSameTreeNode(TreeNode t1,TreeNode t2){

     if(t1==null&&t2==null){
     return true;
     }
     else if(t1==null||t2==null){
     return false;
     }
     if(t1.val != t2.val){
     return false;
     }
     boolean left = isSameTreeNode(t1.left,t2.left);
     boolean right = isSameTreeNode(t1.right,t2.right);
     return left&&right;
    }

  9. 两个二叉树是否互为镜像
   boolean isMirror(TreeNode t1,TreeNode t2){

     if(t1==null&&t2==null){
     return true;
     }
     if(t1==null||t2==null){
     return false;
     }
     if(t1.val != t2.val){
     return false;
     }
     return isMirror(t1.left,t2.right)&&isMirror(t1.right,t2.left);
    }

  10. 翻转二叉树or镜像二叉树
   TreeNode mirrorTreeNode(TreeNode root){

     if(root == null){
     return null;
     }
     TreeNode left = mirrorTreeNode(root.left);
     TreeNode right = mirrorTreeNode(root.right);
     root.left = right;
     root.right = left;
     return root;
    }

  11. 求两个二叉树的最低公共祖先节点
   TreeNode getLastCommonParent(TreeNode root,TreeNode t1,TreeNode t2){

     if(findNode(root.left,t1)){
     if(findNode(root.right,t2)){
     return root;
     }else{
     return getLastCommonParent(root.left,t1,t2);
     }
     }else{
     if(findNode(root.left,t2)){
     return root;
     }else{
     return getLastCommonParent(root.right,t1,t2)
     }
     }
    }
     // 查找节点node是否在当前 二叉树中
    boolean findNode(TreeNode root,TreeNode node){
     if(root == null || node == null){
     return false;
     }
     if(root == node){
     return true;
     }
     boolean found = findNode(root.left,node);
     if(!found){
     found = findNode(root.right,node);
     }
     return found;
    }

  文章来源:https://www.csdn.net/tags/NtzaAg3sODAwMDItYmxvZwO0O0OO0O0O.html