正文 

当前位置： 首页 > java > java教程

java集合与数据结构——二叉树02

RAIN7      2022-04-27     275

关键词：

文章目录

Java集合与数据结构——二叉树(二)初阶面试题


二叉树的前中后遍历


前序遍历

/**
 * 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 

    List<Integer> ret  = new ArrayList<>();

    public List<Integer> preorderTraversal(TreeNode root) 
         if(root == null)
             return ret;
         
          ret.add(root.val);
          preorderTraversal(root.left);
          preorderTraversal(root.right);
           
         return ret;

中序遍历

/**
 * 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 

    List<Integer> ret  = new ArrayList<>();

    public List<Integer> preorderTraversal(TreeNode root) 
    
         if(root == null)
             return ret;
         
        
          preorderTraversal(root.left);
          ret.add(root.val);
          preorderTraversal(root.right);
           
         return ret;

后序遍历

/**
 * 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 

    List<Integer> ret  = new ArrayList<>();

    public List<Integer> preorderTraversal(TreeNode root) 
    
         if(root == null)
             return ret;
         
        
          preorderTraversal(root.left);
          preorderTraversal(root.right);
          ret.add(root.val);
           
         return ret;

获取二叉树的高度



获取二叉树的最大深度

  public int gethigh(TreeNode root) 
  
        if (root == null) 
            return 0;
        

        int leftHeight = gethigh(root.left);
        int rightHeight = gethigh(root.right);

        return (Math.max(leftHeight, rightHeight))+1;
        
     // 可用三目操作符来进行比较
    //  return (leftHeight > rightHeight ? leftHeight + 1 : rightHeight + 1 )  ;

求整颗二叉树的叶子节点数量


遍历思路：

遍历二叉树的每一个节点，如果该节点的左子树和右子树 都为空，那么该节点就为叶子节点，我们要计算叶子节点的数量，定义一个 leafSize ，当节点符合叶子节点的要求时 leafSize ++.

    static int leafSize = 0;
    
    public void getleafSize(TreeNode root) 
     if(root == null)
         return; 
     
     if((root.left == null && root.right == null )
         leafSize++;
     
     
     getleafSize(root.left);
     getleafSize(root.right);

子问题思路：


我们将求二叉树的叶子节点数量这个问题，看成求 二叉树的 左子树的叶子节点 + 右子树的叶子节点

当 root == null 时 返回0

当 root.right == null && root.left == null 时，返回1

  public int getLeafSize2(TreeNode root) 
        
       if(root == null)
           return 0;
       
       
       if(root.right == null && root.left == null)
           return 1;
       
       
       return getLeafSize2(root.left)+getLeafSize2(root.right);

子问题思路：

求第K层 有多少个节点

k=3 时， root 为第一层，我们求第三层相当于求 root.left 的第二层+ root.right 的第二层

同理可得我们最后求的是

root.left.left 的第一层 + root.left.right 的第一层 + root.right.left 的第一层 + root.right.right 的第一层

我们只需要判断此时 k==1 时的节点 是否为空就可以得到第K层的节点，这同时也体现了递归的思路。

我们可以将返回值这样写

return getLevelSize（root.left,k-1） + getLevelSize (root.right,k-1)

 public int getLevelSize(TreeNode root,int k)
        if(root == null)
            return 0;
        
        if(k==1)
            return 1;
        

        return getLevelSize(root.left,k-1)+getLevelSize(root.right,k-1);

查找二叉树中 对应 val 值 的节点

不考虑重复节点！！！

    //  查找二叉树中 对应 val 值 的节点

    TreeNode find(TreeNode root , char val)
        if(root == null)
            return null;
        

        if(root.val == val)
            return root;
        

        TreeNode ret = find(root.left, val);

        if(ret != null)
            return ret;
        

        ret = find(root.right,val);

        if(ret != null)
            return ret;
        

        return null;

判断两颗二叉树是否相同

思路：

考虑 一个为空 一个不为空

两个都为空

两个都不为空时，值不一样

两个都不为空时，首个根的值是一样的

之后我们用递归来判断这两个根节点的左子树和右子树是否相同

/**
 * 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) 
        if(p != null && q == null)
            return false;
        
        
        if(p == null && q !=null)
            return false;
        

        if(p == null && q == null)
            return true;
        
        
        if(p.val != q.val)
            return false;
        

      
   return  isSameTree(p.left,q.left)  && isSameTree(p.right,q.right);

另一棵树的子树

我们来看一组树与子树

思路：

/**
 * 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 root, TreeNode subRoot)
    if(root == null && subRoot != null)
        return false;
    

     if(subRoot == null && root != null)
        return false;
    

    if(subRoot == null && root == null)
        return true;
    

    if(root.val != subRoot.val)
        return false;
    

    return isSameTree(root.left,subRoot.left) && isSameTree(root.right,subRoot.right);


    public boolean isSubtree(TreeNode root, TreeNode subRoot) 
       if(root == null || subRoot == null)
           return false;
       

       if(isSameTree(root,subRoot)== true)
           return true;
       

       if(isSubtree(root.left,subRoot)) return true;
       if(isSubtree(root.right,subRoot)) return true;

       return false;

判断平衡二叉树

什么是平衡二叉树呢？

这颗二叉树的每一个节点的左右子树的高度差绝对值不超过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 int maxDepth(TreeNode root) 
  if (root == null) 
            return 0;
        

        int leftHeight = maxDepth(root.left);
        int rightHeight = maxDepth(root.right);

        return (Math.max(leftHeight, rightHeight))+1;

    

    public boolean isBalanced(TreeNode root) 
      if(root == null) return true;
      
      int rightHeight = maxDepth(root.right);
      int leftHeight  = maxDepth(root.left);

      return 
      Math.abs(rightHeight-leftHeight)<2 && isBalanced(root.left) && isBalanced(root.right);

上述的这种解法 时间复杂度太大了，遍历了每一个节点，在遍历节点的同时还要计算这个节点的深度，相当于右遍历了一遍，所以就是时间复杂度为 O(n^2)

时间复杂度太大了，我们换一种思路。

public int maxHeight(TreeNode root)
     if(root==null)
         return 0;
     

     int leftHeight = maxHeight(root.left);
     int rightHeight = maxHeight(root.right);
// 只要根的左树 或者右树 不满足，那么就会一直返回 -1，最后返回的就是一个负数，那么只要返回的不是正数就不是平衡二叉树

	if(leftHeight>=0 && rightHeight>=0 && Math.abs(leftHeight-rightHeight)<2)
    	return Math.max(leftHeight,rightHeight)+1;
	else
   		return -1;
	




    public boolean isBalanced(TreeNode root) 
		if(root==null)
    		return true;
		

		return maxHeight(root)>=0;

这种解法时间复杂度为 O(n).

这一篇就结束了，今天二叉树就讲到这里，希望大家多多练习，谢谢大家的阅读与欣赏…

二叉树03------进阶编程练习 敬请期待~~

java集合与数据结构二叉树(代码片段)

Java集合与数据结构二叉树树型结构概念重要概念树的表示形式二叉树概念二叉树的基本形态两种特殊的二叉树二叉树的性质二叉树的遍历二叉树基本功能的实现二叉树的前序遍历二叉树的中序遍历二叉树的后序遍历二叉树最大... 查看详情

java集合与数据结构二叉树(代码片段)

Java集合与数据结构二叉树树型结构概念重要概念树的表示形式二叉树概念二叉树的基本形态两种特殊的二叉树二叉树的性质二叉树的遍历二叉树基本功能的实现二叉树的前序遍历二叉树的中序遍历二叉树的后序遍历二叉树最大... 查看详情

java集合与数据结构二叉树(代码片段)

Java集合与数据结构二叉树树型结构概念重要概念树的表示形式二叉树概念二叉树的基本形态两种特殊的二叉树二叉树的性质二叉树的遍历二叉树基本功能的实现二叉树的前序遍历二叉树的中序遍历二叉树的后序遍历二叉树最大... 查看详情

java集合与数据结构优先级队列堆(代码片段)

Java集合与数据结构优先级队列【堆】二叉树的顺序存储存储方式堆(heap)操作-向下调整堆的应用-优先级队列操作-入队列操作-出队列java中的优先级队列堆的其他应用TopK问题堆的其他应用堆排序二叉树的顺序存储存储方式使用数... 查看详情

java集合与数据结构优先级队列堆(代码片段)

Java集合与数据结构优先级队列【堆】二叉树的顺序存储存储方式堆(heap)操作-向下调整堆的应用-优先级队列操作-入队列操作-出队列java中的优先级队列堆的其他应用TopK问题堆的其他应用堆排序二叉树的顺序存储存储方式使用数... 查看详情

数据结构(java)之二叉树

1.       二叉树的逻辑结构a)      定义：二叉树是一种非线性结构，是n个有限元素的集合，由一个根节点与两个不相交的左子树和右子树组成，当集合为空又称为空二叉树，一个元... 查看详情

数据结构学习笔记（二叉树）总结与整理(代码片段)

数据结构学习笔记（二叉树）总结与整理二叉树定义二叉树结构二叉树常用操作二叉树的创建递归方式二叉树的遍历非递归方式二叉树的遍历二叉树的其他功能堆（二叉树的顺序结构）堆的实现二叉树定义概念... 查看详情

数据结构学习笔记（二叉树）总结与整理(代码片段)

数据结构学习笔记（二叉树）总结与整理二叉树定义二叉树结构二叉树常用操作二叉树的创建递归方式二叉树的遍历非递归方式二叉树的遍历二叉树的其他功能堆（二叉树的顺序结构）堆的实现二叉树定义概念... 查看详情

数据结构之二叉树(代码片段)

1.二叉树的基本概念　　二叉树是一种非常常见并实用的数据结构，它结合了有序数组和链表的优点，在二叉树中查找数据与在数组中查找数据一样快，在二叉树中添加删除数据的速度与在链表中一样高效。　　二叉树也称为二... 查看详情

java集合与数据结构——优先级队列（堆）

文章目录一、二叉树的顺序存储1.堆的存储方式2.下标关系二、堆(heap)1.概念2.大/小根堆2.1小根堆2.2大根堆3.建堆操作3.1向下调整4.入队操作4.1向上调整4.2push入队的完整代码展示5.出队操作5.1pop出队代码完全展示6.查看堆顶元素7.TOK... 查看详情

第四节：java集合框架之二叉树

文章目录一：树基本概念（1）树的定义（2）结点分类（3）结点关系（相关术语）（4）常用性质二：二叉树基本概念（1）二叉树定义（2）二叉树五种形态（3）特殊的二叉树（4）二叉树常考性质（5）二叉树存储结构——二叉链... 查看详情

第四节：java集合框架之二叉树

文章目录一：树基本概念（1）树的定义（2）结点分类（3）结点关系（相关术语）（4）常用性质二：二叉树基本概念（1）二叉树定义（2）二叉树五种形态（3）特殊的二叉树（4）二叉树常考性质（5）二叉树存储结构——二叉链... 查看详情

java集合与数据结构优先级队列堆(代码片段)

Java集合与数据结构优先级队列【堆】二叉树的顺序存储存储方式堆(heap)操作-向下调整堆的应用-优先级队列操作-入队列操作-出队列java中的优先级队列堆的其他应用TopK问题堆的其他应用堆排序二叉树的顺序存储存储方式使用数... 查看详情

数据结构树与树的表示二叉树存储结构及其遍历二叉搜索树平衡二叉树堆哈夫曼树与哈夫曼编码集合及其运算

1、树与树的表示什么是树？客观世界中许多事物存在层次关系人类社会家谱社会组织结构图书信息管理分层次组织在管理上具有更高的效率！数据管理的基本操作之一：查找（根据某个给定关键字K，从集合R中找出关键字与K相... 查看详情

数据结构与算法(java)之二叉树(代码片段)

二叉树packagecom.weeks.tree;/***@author达少*@version1.0**实现二叉树数据结构*/publicclassBinaryTreeDemopublicstaticvoidmain(String[]args)//定义二叉树BinaryTreebinaryTree=newBinaryTree();//定义二叉树的节点对象HeroNode 查看详情

数据结构-二叉树的存储结构与遍历

定义二叉树的几个重要性质二叉树的抽象数据类型ADT二叉树的存储结构顺序存储结构链式存储结构结点定义二叉树初始化二叉树的遍历测试二叉树的实现定义一个有穷的结点集合，可以为空。若不为空，则它是由根结点... 查看详情

数据结构与算法系列研究五——树二叉树三叉树平衡排序二叉树avl

树、二叉树、三叉树、平衡排序二叉树AVL一、树的定义  树是计算机算法最重要的非线性结构。树中每个数据元素至多有一个直接前驱，但可以有多个直接后继。树是一种以分支关系定义的层次结构。  a.树是n(≥0)... 查看详情

java数据结构与算法之顺序存储二叉树

顺序存储二叉树顺序存储二叉树的概念从数据存储来看，数组存储方式和树的存储方式可以相互转换，即数组可以转换成树，树也可以转换成数组要求:1)右图的二叉树的结点，要求以数组的方式来存放arr:[1,2,3,4,5,6,6]2)要求在遍历... 查看详情