652. 寻找重复的子树(较难)

给定一棵二叉树，返回所有重复的子树。对于同一类的重复子树，你只需要返回其中任意一棵的根结点即可。

两棵树重复是指它们具有相同的结构以及相同的结点值。

示例 1：

    1
   / \
  2   3
 /   / \
4   2   4
   /
  4

下面是两个重复的子树：

  2
 /
4

和

4

因此，你需要以列表的形式返回上述重复子树的根结点。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/find-duplicate-subtrees

思路：

二叉树，递归

需要知道自己这个节点的子树什么样子，也就是左子树+右子树+自己就是自己的子树的样子，也就是后序遍历的框架，和计算二叉树的节点个数一样，表示子树可以用序列化的样子，将二叉树表示成字符串

https://mp.weixin.qq.com/s/LJbpo49qppIeRs-FbgjsSQ

代码1：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
    public TreeNode constructMaximumBinaryTree(int[] nums) {
        return constructHelper(nums,0,nums.length-1);
    }
    TreeNode constructHelper(int[] nums,int left,int right){
        if(left>right){
            return null;
        }
        //找最大的索引值
        int index =-1;
        int mVal = Integer.MIN_VALUE;
        for(int i=left;i<=right;i++){
            if(mVal< nums[i]){
                index=i;
                mVal=nums[i];
            }
        }
        //开始构造树,其实就是分治思想
        TreeNode root = new TreeNode(mVal);
        root.left=constructHelper(nums,left,index-1);
        root.right=constructHelper(nums,index+1,right);
        return root;
    }
}