共计 1136 个字符,预计需要花费 3 分钟才能阅读完成。
老话放在后面 依据题意,思考一个二叉树节点须要做什么,到底用什么遍历程序就分明了
寻找反复的子树
对于某个节点,如何晓得本人是不是反复的
1. 以我为根的这棵二叉树(子树) 长啥样?
2. 以其余节点为根的子树都长啥样?
咱们如何晓得本人长啥样呢,能够用后序遍历的框架来解决
void traverse(TreeNode root){
traverse(root.left);
traverse(root.right);
}
这样咱们就晓得本人长成什么样了
所以,咱们能够通过 拼接字符串 的形式来把二叉树序列化,看下代码
String traverse(TreeNode root){ | |
// 对于空节点,能够用一个特殊字符来示意 | |
if(root==null){return "#";} | |
// 将左右子树序列化为字符串 | |
String left=traverse(root.left); | |
String right=traverse(root.right); | |
// 后序遍历地位 | |
// 左右子树加上本人,就是以本人为根的二叉树 | |
String subTree=left+","+right+","+root.val; | |
return subTree; | |
} |
咱们用非数字的非凡符 #示意空指针,并且用字符,分隔每个二叉树节点值,这属于序列化二叉树的套路。
对于每个节点来说,递归函数中的 subTree 变量就能够形容以该节点为根的二叉树
接下来,如何晓得他人长什么样?
咱们能够创立一个内部变量,通过将序列化后的后果保留在其中,那么咱们就能够晓得他人是不是曾经有过了,如果曾经存在的话,东哥的代码也解释了一开始应用的是 Set 构造,那么做完比照的后果就有多个反复的 res, 所以应用 HashMap。
HashMap<String,Integer> memo=new HashMap<>(); | |
LinkedList<TreeNode> res=new LinkedList<>(); | |
List<TreeNode> findDuplicationSubtrees(TreeNode root){traverse(root); | |
return res; | |
} | |
String traverse(TreeNode root){if(root==null){return "#";} | |
String left=traverse(root.left); | |
String right=traverse(root.right); | |
String subTree=left+","+right+","+root.val; | |
int freq=meomo.getOrDefault(subTree,0); | |
if(freq==1){res.add(root); | |
} | |
memo.put(subTree,freq+1); | |
return subTree; | |
} |
正文完