• 能带你起飞的【数据结构】成王第十篇:二叉树3

    目录

    前言

    检查两棵树是否相同

    完整代码

    另一颗树的子树 

    完整代码

     判断一颗二叉树是否是平衡二叉树

    完整代码

    优化写法

    完整代码

    对称二叉树 

    完整代码

    二叉树的构建及遍历 

    完整代码

    二叉树的分层遍历

    完整代码

    前言

     

    检查两棵树是否相同

    100. 相同的树 - 力扣（LeetCode）

    给你两棵二叉树的根节点 p 和 q ，编写一个函数来检验这两棵树是否相同。

     什么是两棵相同的二叉树?

    节点的值相同且树的结构也是相同的

     一棵树的根节点是p,第二棵树的根节点是q

    判断是p这棵树和q这棵树是不是两棵相同的树,除了两棵树都不为空的前提下,一定要保证他们里面的值是一样的,此时只能证明p这棵树的根节点和q这棵树的根节点是相同的.那么左树是不是也得判断,看下图:

    p和q这两棵树要相同除了保证根结构和值一样的情况下,p的左树和q的左树也必须相同.p的右树和q的右树也必须相同 ,才能证明两棵树是相同的树.左树也有根也有左树右树,右树也有根也有左树右树.

    判断方式都是一样的,都是根不为空,判断根的左和根的右,这里主要围绕两个点:节点的值是否相同,树的结构是否相同.

    如何判断结构是否相同呢?

     上述这种就属于结构不同,这样我们就可以推导出来:

    如果一个为空,一个不为空,结构不相同

    再来看下面一种情况

     此时p == null q == null 说明此时p和q是两个相同的树

    再看另外一种情况:

     虽然p和q都不为空,但是p.val != q.val,此时p和q就不是相同的树 

    只有在p和q都不为空,且值都一样的情况下,那么我们就在这种情况下遍历这个二叉树

    p和q都不为空,且值都一样的,那么再去递归左树,看左树相不相同,左树递归完,左树相同,再来看p的右树相不相同,只有左树右树都相同的情况下,那么我们说这是两棵相同的二叉树

    完整代码

    1. class Solution {
    2.     public boolean isSameTree(TreeNode p, TreeNode q) {
    3.         if(p == null && q == null) return true;
    4.  
    5.         if(p == null && q != null || p != null && q == null){
    6.             return false;
    7.         }
    8.         if(p.val != q.val){
    9.             return false;
    10.         }
    11.         return isSameTree(p.left,q.left) && isSameTree(p.right,q.right);
    12.         
    13.     }
    14.  
    15. }

    另一颗树的子树 

    572. 另一棵树的子树 - 力扣（LeetCode）

    给你两棵二叉树 root 和 subRoot 。检验 root 中是否包含和 subRoot 具有相同结构和节点值的子树。如果存在，返回 true ；否则，返回 false 。

    二叉树 tree 的一棵子树包括 tree 的某个节点和这个节点的所有后代节点。tree 也可以看做它自身的一棵子树。

     还有下面这情况

     root和subRoot两棵相同的情况下也属于子树

    1.先判断两棵树是不是两棵相同的树

    2.如果不是,分别判断subRoot是不是root的左子树或者右子树

    我们可以先通过上面的题来判断是不是同一棵树

    完整代码

    1. class Solution {
    2.     public boolean isSameTree(TreeNode p, TreeNode q) {
    3.         if(p == null && q == null) return true;
    4.  
    5.         if(p == null && q != null || p != null && q == null){
    6.             return false;
    7.         }
    8.         if(p.val != q.val){
    9.             return false;
    10.         }
    11.         return isSameTree(p.left,q.left) && isSameTree(p.right,q.right);
    12.         
    13.     }
    14.     public boolean isSubtree(TreeNode root, TreeNode subRoot) {
    15.         if(root == null || subRoot == null) return false; 
    16.         if(isSameTree(root,subRoot)){
    17.             return true;
    18.         }
    19.         if(isSubtree(root.left,subRoot)){
    20.             return true;
    21.         }
    22.          if(isSubtree(root.right,subRoot)){
    23.             return true;
    24.         }
    25.         return false;
    26.       
    27.     }
    28. }

     判断一颗二叉树是否是平衡二叉树

    110. 平衡二叉树 - 力扣（LeetCode）

    给定一个二叉树，判断它是否是高度平衡的二叉树。

    本题中，一棵高度平衡二叉树定义为：

    一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1 。

     上图这个棵树就是一棵平衡二叉树,因为左树高度值为1,右树高度值为2,两个绝对值差不超过1

    一棵树要是平衡二叉树,那么他的每棵子树也必须是平衡二叉树

    我们看下图的特殊情况:

     3这棵树是平衡的,但是9这棵不是平衡的,20这棵也不是平衡的,所以这就不是平衡二叉树

    1.root 左树的高度 - 右树的高度 <= 1

    2.root的左树是平衡的,右树也是平衡的

    我们要先求出树的高度

    完整代码

    1. class Solution {
    2.     public int height(TreeNode root){
    3.         if(root == null){
    4.             return 0;
    5.         }
    6.            int leftHeight = height(root.left);
    7.             int rightHeight = height(root.right);
    8.             return (leftHeight > rightHeight) ? (leftHeight + 1) : (rightHeight + 1);
    9.     }
    10.     public boolean isBalanced(TreeNode root) {
    11.         if(root == null){
    12.             return true;
    13.         }
    14.         int left = height(root.left);
    15.         int right = height(root.right);
    16.         return Math.abs(left-right) <= 1 && isBalanced(root.left) && isBalanced(root.right);
    17.  
    18.  
    19.  
    20.     }
    21. }

    优化写法

     

     求左树的高度

    root一直往下递归,递归到左树最后一个节点.再递归,发现最后一个节点的左树为空,右树也为空,这个时候我们就可以判断一下,leftHeight - rightHeight的绝对值是否<=1,如果满足就返回leftHeight和rightHeight的最大值加1.

    如果不满足看图

     此时root再往左边递归就是null,然后返回一个0在递归右树,返回一个2

     此时高度差就不满足<=1了,我们就让它返回-1

    此时的root返回了一个负数,再去遍历root的右树,此时root返回的是一个0,此时求绝对值-1-0 = 1.那么又变成<=1了,但是明明左树已经不平衡了.

    所以我们要判断每一个高度拿回来的是不是负数,因为本身求高的返回值不可能是负数,所以我们要判断一下,只有leftHeight >= 0,rightHeight >= 0的情况下

    完整代码

    1. class Solution {
    2.  
    3.     public int height(TreeNode root){
    4.         if(root == null) return 0;
    5.  
    6.         int leftHieght = height(root.left);
    7.         int rightHieght = height(root.right);
    8.        if(leftHieght >= 0 && rightHieght >= 0 && Math.abs(leftHieght - rightHieght) <= 1){
    9.            return Math.max(leftHieght,rightHieght) + 1;
    10.        }else{
    11.            return -1;
    12.        }
    13.  
    14.     }
    15.     public boolean isBalanced(TreeNode root) {
    16.         if(root == null) return true;
    17.         
    18.         return  height(root) >= 0;
    19.        
    20.     }
    21. }

    对称二叉树 

    101. 对称二叉树 - 力扣（LeetCode）

    给你一个二叉树的根节点 root ， 检查它是否轴对称

     

     

    完整代码

    1. lass Solution {
    2.     public boolean isSymmetricchild(TreeNode leftTree,TreeNode rightTree) {
    3.         if(leftTree != null && rightTree == null){
    4.             return false;
    5.         }
    6.          if(leftTree == null && rightTree != null){
    7.             return false;
    8.         }
    9.        if(leftTree == null && rightTree == null){
    10.            return true;
    11.        }
    12.        if(leftTree.val != rightTree.val){
    13.            return false;
    14.        }
    15.        return isSymmetricchild(leftTree.left,rightTree.right) && isSymmetricchild(leftTree.right,rightTree.left);
    16.  
    17.     }
    18.     public boolean isSymmetric(TreeNode root) {
    19.         if(root == null){
    20.             return true;
    21.         }
    22.         return isSymmetricchild(root.left,root.right);
    23.  
    24.     }
    25. }

    二叉树的构建及遍历 

    二叉树遍历_牛客题霸_牛客网 (nowcoder.com)

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

     

    给定的#为空

    题目给定的是前序遍历的结果,那么我们构建这棵二叉树的时候,也是要用前序遍历的方式来进行构建.定义一个i来遍历这个字符串,当i没有遇到#号的时候,我们就new一个节点,里面的值就是A,这样根root就有了,因为是前序遍历,先构建root的左,在构建root的又右.意味着我们就可以递归当前的这个函数

    完整代码

    1. class TreeNode{
    2.     public char val;
    3.     public TreeNode left;
    4.     public TreeNode right;
    5.     
    6.     public TreeNode (char val){
    7.         this.val = val;
    8.     }
    9. }
    10. public class Main {
    11.     public static int i = 0;
    12.     public static TreeNode createTree(String str){
    13.         TreeNode root = null;
    14.         if(str.charAt(i) != '#'){
    15.             root = new TreeNode(str.charAt(i));
    16.             i++;
    17.             root.left = createTree(str);
    18.             root.right = createTree(str);
    19.         }else{
    20.             i++;
    21.         }
    22.         return root;
    23.     }
    24.     public static void inorder (TreeNode root){
    25.         if(root == null) return;
    26.         inorder(root.left);
    27.         System.out.print(root.val + " ");
    28.         inorder(root.right);
    29.     }
    30.     
    31.     public static void main(String[] args) {
    32.         Scanner in = new Scanner(System.in);
    33.         // 注意 hasNext 和 hasNextLine 的区别
    34.         while (in.hasNextLine()) { // 注意 while 处理多个 case
    35.            String str = in.nextLine();
    36.             TreeNode root = createTree(str);
    37.             inorder(root);
    38.         }
    39.     }
    40. }

    二叉树的分层遍历

    102. 二叉树的层序遍历 - 力扣（LeetCode）

     和判断是否是一棵完全二叉树的写法近乎相同,都要用到队列

    如果root不为空我们就把它放到队列

     紧接着判断队列为不为空,不为空就弹出队列的一个元素,把A给cur,同时把A进行打印

    再判断A的左为不为空,不为空把A的左放到队列里, 右为不为空,不为空把A的右放到队列里

    然后再来看队列为不为空,不为空弹出队头元素B,把B给cur,1同时打印B

     下一步就是B的左和B的右

    此时再判断队列为不为空

    依次往后推,直到队列整个为空,就遍历完我们的二叉树了

    完整代码

     

    1. class Solution {
    2.     public List<List<Integer>> levelOrder(TreeNode root) {
    3.       List<List<Integer>> ret = new ArrayList<>();
    4.         if(root == null) return ret;
    5.         Queue<TreeNode> queue = new LinkedList<>();
    6.         queue.offer(root);
    7.         while(!queue.isEmpty()){
    8.             int size = queue.size();//这个值代表当前层有多少个节点
    9.              List<Integer> list = new ArrayList<>();
    10.             while(size != 0){
    11.                 TreeNode cur = queue.poll();
    12.                 list.add(cur.val);
    14.                if(cur.left != null){
    15.                  queue.offer(cur.left);
    16.             }
    17.              if(cur.right != null){
    18.                  queue.offer(cur.right);
    19.             }
    20.                size--;
    21.                 
    22.             }
    23.             ret.add(list);
    25.         }
    26.         return ret;
    28.     }
    29. }

     

  • 相关阅读:
    C语言 - 四种方法解决杨辉三角问题
    Sping boot 前后端分离 开发api 或服务端直接重定向某个域名
    FreeRTOS教程4 消息队列
    【Flutter组件】Dialog使用说明
    面试题: LEAD 和 LAG 求每个用户的页面停留时长
    C#获取字母后的数字
    oracle、mysql、postgresql数据库的几种表关联方法
    【STL】：list的模拟实现
    基于JSP的网上书城平台【数据库设计、源码、开题报告】
    C++ call python with cmake
  • 原文地址：https://blog.csdn.net/m0_64397675/article/details/125462879