欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

给定两个非空二叉树 s 和 t,检验s 中是否包含和 t 具有相同结构和节点值的子树

程序员文章站 2022-06-21 14:13:05
思路:1、在s为根的树中,查找t这个结点(只要结点的值相等即可,不要求同一个结点)2、如果没找到,就意味着,在s为根的树中一定不包含和 t 具有相同结构和节点值的子树3、如果找到了,检查找到的这个结点为根的数是否和t树相等,如果不想等,接着找/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right;...

思路:

1、在s为根的树中,查找t这个结点(只要结点的值相等即可,不要求同一个结点)
2、如果没找到,就意味着,在s为根的树中一定不包含和 t 具有相同结构和节点值的子树
3、如果找到了,检查找到的这个结点为根的数是否和t树相等,如果不想等,接着找

/**
 * 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 true; } if(p == null || q == null){ return false; } return p.val == q.val &&isSametree(p.left,q.left)&&isSametree(p.right,q.right); } public boolean search(TreeNode root,TreeNode t){ if(root == null){ return false; } if(isSametree(root,t)){ return true; } if(search(root.left,t)){ return true; } return search(root.right,t); } public boolean isSubtree(TreeNode s, TreeNode t) { return search(s,t); } } 

本文地址:https://blog.csdn.net/weixin_46655672/article/details/108875644