本文主要是介绍检查子树00,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
题目链接
检查子树
题目描述
注意点
- 树的节点数目范围为[0, 20000]
解答思路
- 递归判断t1和t2的val是否相同,如果相同,则继续递归判断其左右子树的值是否都相同,如果都相同则返回true;如果不相同,则继续递归判断t1的左右子树和t2的val是否相同
- 需要注意的是,如果t1和t2的val相同,在判断其左右子树的值是否相同时,如果不同,则直接返回false;而在判断t1和t2的val不同时,不应该直接返回false,还需要判断t1的左右子树与t2是否相同,所以还需要传递isRoot记录t2是否是根节点
代码
/*** Definition for a binary tree node.* public class TreeNode {* int val;* TreeNode left;* TreeNode right;* TreeNode(int x) { val = x; }* }*/
class Solution {public boolean checkSubTree(TreeNode t1, TreeNode t2) {return preOrder(t1, t2, true);}public boolean preOrder(TreeNode t1, TreeNode t2, boolean isRoot) {if (t1 == null && t2 == null) {return true;}if (t1 == null || t2 == null) {return false;}if (t1.val != t2.val) {if (!isRoot) {return false;}return preOrder(t1.left, t2, isRoot) || preOrder(t1.right, t2, isRoot);}boolean flag = preOrder(t1.left, t2.left, false) && preOrder(t1.right, t2.right, false);if (flag) {return true;}return preOrder(t1.left, t2, isRoot) || preOrder(t1.right, t2, isRoot);}
}
关键点
- 递归的思路
- 注意递归判断t1的某个节点和t2的根节点、t1的某个节点和t2和某个节点不相同的分类情况
这篇关于检查子树00的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!