二叉树基本操作和相关列题

 【前言】

         最近复习二叉树相关习题 ,根据课件练习几道基础习题 分享给大家

         树是数据结构中的重中之重,尤其以各类二叉树基础问题为重要点,希望通过总结二叉树基础问题来深入了解二叉树。

二叉树基本操作和相关列题

【 二叉树概念简介 】

  结点的度 :一个结点含有子树的个数称为该结点的度;    树的度一棵树中,所有结点度的最大值称为树的度;    叶子结点或终端结点度为 0 的结点称为叶结点;    双亲结点或父结点若一个结点含有子结点,则这个结点称为其子结点的父结点;    孩子结点或子结点一个结点含有的子树的根结点称为该结点的子结点;     根结点一棵树中,没有双亲结点的结点;    结点的层次从根开始定义起,根为第 1层,根的子结点为第2层,以此类推   树的高度或深度树中结点的最大层次;  

【二叉树性质】

1. 若规定根结点的层数为1,则一棵非空二叉树的第i层上最多有 (2^(i -1))(i>0)个结点 2. 若规定只有根结点的二叉树的深度为1,则深度为K的二叉树的最大结点数是2^k-1(k>=0) 3. 对任何一棵二叉树, 如果其叶结点个数为 n0, 度为2的非叶结点个数为 n2,则有n0=n2+1 4. 具有n个结点的完全二叉树的深度k为 log(n+1)  上取整

二叉树基本操作和相关列题



二叉树基本操作和相关列题

 

 

 【二叉树基础知识

      【 获得树的节点个数】
int size(Node root){//获得树的节点个数

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

【获得叶子节点个数】

  static leafcount = 0;
 void  getLeafNodeCount(TreeNode root){
  if(root == null) return ;
  if(root.left == null && root.right == null){
     leafcount ++;

  }
     getLeafNodeCount( root.left);
     getLeafNodeCount( root.right);

}

【// 获取第K层节点的个数 】

int getKLevelNodeCount(Node root, int k){
 if(root == null || k < 0) return -1;
 if(k == 1){
   return 1;
 }
   return getKLevelNodeCount(root.left,k-1) + getKLevelNodeCount(root.right, k-1);
 
}

【 获取二叉树的高度】
int getHeight(Node root){
        if(root == null) return 0;//
      int high1 = getHeight( root.left);//递归树的左边    计算高度
      int high2 = getHeight(root.right);//递归树的右边  计算高度
      if(high1 > high2) {
          return high1 + 1;//返回时加上根节点
      }else{
          return high2 + 1;
      }
【检测值为value的元素是否存在】

    TreeNode find(Node root, int val){//检测值是否存在
        if(root == null) return null;
         if(root.val = val) return root;

      TreeNode val1 = find( root.left,  val)
              if( val1!= null){
                  return val1
              }
         TreeNode  val2 = find( root.right, val);
              if(val2 != null){
                  return val2;
              }
              return null;

【判断一棵树是不是完全二叉树】
 public boolean isBalanced(TreeNode root) {
       return high(root) > 0;
    }
   public int high( TreeNode root1 ){
       if(root1 ==  null ) return 1;
     int high1 =   high(root1.left );//递归出树的左数高度
     int high2 =   high(root1.right);// 右树高度
      if(high1 == -1 || high2 == -1 || Math.abs(high1-high2 ) >1){//-1指遇到null是会返回-1 表明没有下个节点
         return -1;
     }else{
         return Math.max(high1,high2)+1;
     } 
【检查两颗树是否相同】
  public boolean isSameTree(TreeNode p, TreeNode q) {
      if(p == null && q == null) return true;//p和q 同时为null时表明 递归结束 结点个数相同
      if(p == null || q == null) return false;// 两者只有一个为null 另一个还没有走完 返回false
      if(p.val != q.val ) return false;//比较两者的值
      
      
     return isSameTree(p.left, q.left) && isSameTree( p.right, q.right) ; //同时递归树的左边和右边
      
     
【另一颗树的子树】
public boolean isSameTree(TreeNode p, TreeNode q) {//判断其是否和其子树相同 和上一个判断相同的树一致
      if(p == null && q == null) return true;
      if(p == null || q == null) return false;
      if(p.val != q.val ) return false;
      
      
     return isSameTree(p.left, q.left) && isSameTree( p.right, q.right) ;     
    }
     
    public boolean isSubtree(TreeNode root, TreeNode subRoot) {
      if(root == null || subRoot == root){
          return false;
      }
    if(isSameTree(root,subRoot)){//判断根节点相同
      return true;
    }
    if (isSubtree(root.left,subRoot )){//递归树的左侧是否与子树相同
        return true;
    }
    if(isSubtree(root.right,subRoot )){//递归树的右侧是否与子树相同
        return true;
    }
    
return false;
    }
【二叉树最大深度】
class Solution {
    public int maxDepth(TreeNode root) {
       if(root == null) return 0;
      int high1 =  maxDepth(root.left);//递归左侧 求出高度
      int high2 =  maxDepth(root.right);//递归右侧 求出高度
      if(high1 > high2){两者进行比较   大的一方加上起初根节点 返回
          return high1+1;
      }else{
          return high2+1;
      }
    }
}
【判断一颗二叉树是否是平衡二叉树】
class Solution {
    public boolean isBalanced(TreeNode root) {
       return high(root) > 0;
    }
   public int high( TreeNode root1 ){
       if(root1 ==  null ) return 1;
     int high1 =   high(root1.left );//获取左树高度
     int high2 =   high(root1.right);//获取右树高度
     if(high1 == -1 || high2 == -1 || Math.abs(high1-high2 ) >1){
         return -1;
     }else{
         return Math.max(high1,high2)+1;//
     } 
    
   }
    
     
}
【对称二叉树】
class Solution {
    public boolean isSymmetric(TreeNode root) {
    return issame(  root, root);
    }
    public boolean issame(TreeNode root1,TreeNode root2){//
   if(root1 == null && root2 == null) return true; 当两个根节点都为null 说明都到了最后一个节点
   if(root1 == null || root2 == null) return false;//只有其中一个节点到达null 
       
        return root1.val == root2.val && issame( root1.left, root2.right) && issame( root1.right, root2.left);// 同时递归 因为是对称 左右要分开
   
}
}
【二叉树的构建及遍历】
import java.util.*;
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);
         while (in.hasNextLine()) {  
            String str = in.nextLine();
            TreeNode root = createTree(str);
            inorder(root);
    }
}
}
【二叉树的分层遍历 】
class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) {
       List<List<Integer>> ret = new ArrayList<>();//定义一个链表进行存储
      Queue<TreeNode> myqueue = new LinkedList<>();//栈里存放元素
       if(root == null) return ret;
        myqueue.offer(root);//将根节点放入栈中
       while(!myqueue.isEmpty()){
           List<Integer> list = new LinkedList<>();
           int size = myqueue.size();//计算出此时栈中的元素个数
           while(size != 0){
               TreeNode cur = myqueue.poll();
               list.add(cur.val);将栈中最顶上一个元素 放入 链表中
               if(cur.left != null){这里分为两个情况 
                   myqueue.offer(cur.left);
               }
               if(cur.right != null){
                   myqueue.offer(cur.right);
               }
               size--;
           } 
            ret.add(list);
       }
      return ret;
        }
    }
【给定一个二叉树, 找到该树中两个指定节点的最近公共祖先】
class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if(root == null) return null;
        Stack<TreeNode> stack1 = new Stack<>();
        getPath( root, p, stack1);
        Stack<TreeNode> stack2  = new Stack<>();
        getPath(  root,q, stack2);
        int size1 = stack1.size();
        int size2 = stack2.size();
        if(size1 > size2){
             int size = size1-size2;
             while(size != 0){
                 stack1.pop();
                 size--;
             }
           while(!stack1.empty() && !stack2.empty()){
               if(stack1.peek() == stack2.peek()){
                   return stack1.pop();
               }else{
                   stack1.pop();
                   stack2.pop();
               }
           }
           
         }else{
              int size = size2-size1;
             while(size != 0){
                 stack2.pop();
                 size--;
             }
           while(!stack1.empty() && !stack2.empty()){
               if(stack1.peek() == stack2.peek()){
                   return stack1.pop();
               }else{
                   stack1.pop();
                   stack2.pop();

         }
【二叉树搜索树转换成排序双向链表】
/**
public class TreeNode {
    int val = 0;
    TreeNode left = null;
    TreeNode right = null;

    public TreeNode(int val) {
        this.val = val;

    }

}
*/
public class Solution {
           TreeNode pre = null;
     public void inorder(TreeNode pCur) {
      if(pCur == null) return ;
         inorder(pCur.left);
         pCur.left = pre;
         if(pre != null){
            pre.right =  pCur;
         }
         pre = pCur;
         inorder(pCur.right);
     
     }
    public TreeNode Convert(TreeNode pRootOfTree) {
        if(pRootOfTree == null) return null;
        inorder(pRootOfTree);
        TreeNode head = pRootOfTree;
        while(head.left != null){
            head = head.left;
        }
        return head;
    }
}
. 【二叉树前序非递归遍历实现 】
class Solution {
     
    public List<Integer> preorderTraversal(TreeNode root) {
    List<Integer> mylist = new ArrayList<Integer>();
     Stack<TreeNode> stack = new Stack<>();
              TreeNode  cur = root;
              while( cur != null || !stack.isEmpty()) {
                  while (cur != null) {
                      stack.push(cur);
                     // System.out.println(cur);
                     mylist.add(cur.val);
                      cur = cur.left;

                  }
                  TreeNode pre = stack.pop();
                  cur = pre.right;
}
                return mylist;
    }
}
. 【二叉树中序非递归遍历实现】
/**
 * 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 List<Integer> inorderTraversal(TreeNode root) {
   List<Integer> mylist = new ArrayList<Integer>();//
     Stack<TreeNode> stack = new Stack<>();
              TreeNode  cur = root;
              while( cur != null || !stack.isEmpty()){
                 while(cur != null){
                 stack.push(cur);将根节点存放在 栈中
                  cur = cur.left;//将cur定义为左侧树
              }
              TreeNode pre = stack.pop();
              mylist.add(pre.val);
              cur = pre.right;将cur定义为右侧树
    }
              return mylist;

    }
}
【二叉树后序非递归遍历实现】
/**
 * 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 List<Integer> postorderTraversal(TreeNode root) {
   List<Integer> mylist = new ArrayList<Integer>();
     Stack<TreeNode> stack = new Stack<>();
              TreeNode  cur = root;
              TreeNode top = null;
              while( cur != null || !stack.isEmpty()) {
                  while (cur != null) {
                     
                      stack.push(cur);
                     // System.out.println(cur);
                    
                      cur = cur.left;

                  }
                    
                  TreeNode pre = stack.peek();
                  //mylist.add(pre.val);
                    
                    if(pre.right == null || pre.right == top){
                        TreeNode pres = stack.pop();
                         mylist.add(pres.val);
                         top = pre;
                    }else{
                        cur = pre.right;
                    }
                   
}
              
                return mylist;
    }
}

上一篇:clickhouse常见异常以及错误码解决


下一篇:【二叉树】二叉树的锯齿形层序遍历