• 572. 另一棵树的子树


    572. 另一棵树的子树

    原题

    /**
     * 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;
     *     }
     * }
     */
     /**
     解题思路
    要判断一个树 t 是不是树 s 的子树,那么可以判断 t 是否和树 s 的任意子树相等。那么就转化成 100. Same Tree。 即,这个题的做法就是在 s 的每个子节点上,判断该子节点是否和 t 相等。
    
    判断两个树是否相等的三个条件是与的关系,即:
    
    当前两个树的根节点值相等;
    并且,s 的左子树和 t 的左子树相等;
    并且,s 的右子树和 t 的右子树相等。
    而判断 t 是否为 s 的子树的三个条件是或的关系,即:
    
    当前两棵树相等;
    或者,t 是 s 的左子树;
    或者,t 是 s 的右子树。
    判断 是否是相等的树 与 是否是子树 的代码简直是对称美啊~
      */
    class Solution {
        public boolean isSubtree(TreeNode root, TreeNode subRoot) {
            if(root==null&&subRoot==null){
                return true;
            }
            if(root==null||subRoot==null){
                return false;
            }
            //判断当前两棵树相等,还是root左子树包含,还是右子树包含
            return isSametree(root,subRoot)||isSubtree(root.left,subRoot)||isSubtree(root.right,subRoot);
        }
    
        //判断两棵树是否相等
        public boolean isSametree(TreeNode root,TreeNode subRoot){
            if(root==null&&subRoot==null){
                return true;
            }
            if(root==null||subRoot==null){
                return false;
            }
            return root.val==subRoot.val&&isSametree(root.left,subRoot.left)&&isSametree(root.right,subRoot.right);
        }
    
    }
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
  • 相关阅读:
    优化开启Nginx的最大并发性能【支持2万到3万并发量!】
    七、安装Centos7+8系统+超级优化
    图像文件的操作MATLAB基础函数使用
    学习笔记(11)js事件
    openresty定时任务
    【MCU】栈溢出问题
    某OA系统审计小记
    如何在移动钱包中搭建一个小程序应用商店
    驱动保护进程 句柄降权 杀软自保 游戏破图标技术原理和实现
    RK3588 hdmiout调试(二)
  • 原文地址:https://blog.csdn.net/qq_64403619/article/details/133583055