做网站的价格,如何广告推广,网站制作经费预算,制作网页框架博主简介#xff1a;努力学习的22级计算机科学与技术本科生一枚#x1f338;博主主页#xff1a; 是瑶瑶子啦每日一言#x1f33c;: 你不能要求一片海洋#xff0c;没有风暴#xff0c;那不是海洋#xff0c;是泥塘——毕淑敏 目录 一、核心二、题目 一、核心
我们清楚… 博主简介努力学习的22级计算机科学与技术本科生一枚博主主页 是瑶瑶子啦每日一言: 你不能要求一片海洋没有风暴那不是海洋是泥塘——毕淑敏 目录 一、核心二、题目 一、核心
我们清楚在二叉树的遍历中通常有三个位置
前序位置中序位置后序位置
今天我们来具体总结一下其中的两个位置 前序:它能获得的信息当前节点但是不难获得左右节点或者可以叫做子树的信息一般大多数情况。后序:当前节点信息左右子树信息。所以当一个二叉树的题目在遍历的过程中不仅需要看遍历到的当前节点的信息时还要看其子树的信息那么通常要在后序位置上做文章利用好递归函数的返回值——获取子树信息。—— 本质还是第二种二叉树问题分解成子问题利用好返回值 下面详细讲一个题目,来体会一下 二、题目
652. 寻找重复的子树 思路 首先明确的是这题的本质还是遍历。因为每个节点为根就是一个子树找重复子树那么每个节点都要遍历到这是毋庸置疑的。⭐遍历到了这个节点我如何知道以这个节点为根的子树是什么样子的呢——根节点左右子树。这个时候只知道此时的根节点什么样子没什么用关键是也要知道以它为根的左右子树什么样子。那么这个时候要在后序位置上做文章了。因为后序位置处于一个既遍历到了根节点也遍历到了子树节点的一个位置即既有根节点信息又有以此根节点为根的子树信息。⭐其次可以利用前面所讲的二叉树的序列化以字符串的形式来把该二叉树存起来再用字符串的哈希表来判断是否重复。 ♀️代码
/*** 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 {MapString, Integer map new HashMap(); //存储二叉树的序列化字符串判断是否重复ListTreeNode ans new ArrayList(); //存储答案即有重复子树的根节点public ListTreeNode findDuplicateSubtrees(TreeNode root) {dfs(root); //遍历二叉树return ans;}//这个遍历函数的作用序列化一颗二叉树返回序列化字符串利用好返回值String dfs(TreeNode root){if(root null) return#;StringBuilder sb new StringBuilder();//前序位置sb.append(root.val).append(,);//中序sb.append(dfs(root.left)).append(dfs(root.right));//获取左右子树信息//后序位置String key sb.toString();//存储整个二叉树信息map.put(key, map.getOrDefault(key, 0) 1);if(map.get(key) 2) ans.add(root); //一旦超过2个。就addreturn key;}
}若有疑问的地方欢迎随时在评论区or私信找瑶瑶子交流讨论 Java岛冒险记【从小白到大佬之路】 LeetCode每日一题–进击大厂 Go语言核心编程 算法
