给定一棵二叉树 root,返回所有重复的子树。
对于同一类的重复子树,你只需要返回其中任意一棵的根结点即可。
如果两棵树具有相同的结构和相同的结点值,则它们是重复的。
示例 1:
输入:root = [1,2,3,4,null,2,4,null,null,4]
输出:[[2,4],[4]]
示例 2:
输入:root = [2,1,1]
输出:[[1]]
示例 3:
输入:root = [2,2,2,3,null,3,null]
输出:[[2,3],[3]]
提示:
树中的结点数在[1,10^4]范围内。
-200 <= Node.val <= 200
var findDuplicateSubtrees = function(root) {
let i = 0
const h = new Map, ans = [], d = n => {
if (n == null) return 0
const s = n.val + ',' + d(n.left) + ',' + d(n.right)
if (h.has(s) === false) h.set(s, [++i, 0])
else if (h.get(s)[1] === 0) {
ans.push(n)
h.get(s)[1] = 1
}
return h.get(s)[0]
}
return d(root), ans
};
function findDuplicateSubtrees(root: TreeNode | null): Array<TreeNode | null> {
const h = new Map, ans = []
let i = 0
const d = n => {
if (n === null) return 0
const s = n.val + ',' + d(n.left) + ',' + d(n.right)
if (h.has(s)) {
if (h.get(s)[1] === 0) {
ans.push(n)
h.get(s)[1] = 1
}
} else {
h.set(s, [++i, 0])
}
return h.get(s)[0]
}
return d(root), ans
};
class Solution {
private $h = array();
private $i = 0;
private $ans = array();
function d($n) {
if ($n === null) return 0;
$s = $n->val . ',' . $this->d($n->left) . ',' . $this->d($n->right);
if ($this->h[$s] === null) {
$this->h[$s] = array(++$this->i, 0);
} else {
if ($this->h[$s][1] === 0) {
$this->ans []= $n;
$this->h[$s][1] = 1;
}
}
return $this->h[$s][0];
}
function findDuplicateSubtrees($root) {
$this->d($root);
return $this->ans;
}
}
func findDuplicateSubtrees(root *TreeNode) []*TreeNode {
i, h, ans := 0, map[[3]int][2]int{}, []*TreeNode{}
var d func(n *TreeNode) int
d = func(n *TreeNode) int {
if n == nil {
return 0
}
s := [3]int{n.Val, d(n.Left), d(n.Right)}
if _, ok := h[s]; ok == false {
i++
h[s] = [2]int{i, 0}
} else if (h[s][1] == 0) {
ans = append(ans, n)
h[s] = [2]int{h[s][0], 1}
}
return h[s][0]
}
d(root)
return ans
}
class Solution {
private int i = 0;
private Map<String, int[]> h = new HashMap<String, int[]>();
private List<TreeNode> ans = new ArrayList<TreeNode>();
private int d(TreeNode n) {
if (n == null) return 0;
String s = n.val + "," + d(n.left) + "," + d(n.right);
if (h.containsKey(s) == false) {
i++;
h.put(s, new int[]{i, 0});
} else if (h.get(s)[1] == 0) {
ans.add(n);
h.get(s)[1] = 1;
}
return h.get(s)[0];
}
public List<TreeNode> findDuplicateSubtrees(TreeNode root) {
d(root);
return ans;
}
}
public class Solution {
private Dictionary<string, int[]> h = new Dictionary<string, int[]>();
private int i = 0;
private List<TreeNode> ans = new List<TreeNode>();
public int d(TreeNode n) {
if (n == null) return 0;
string s = n.val + "," + d(n.left) + "," + d(n.right);
if (h.ContainsKey(s) == false) {
h.Add(s, new int[2]{++i, 0});
} else if (h[s][1] == 0) {
h[s][1] = 1;
ans.Add(n);
}
return h[s][0];
}
public IList<TreeNode> FindDuplicateSubtrees(TreeNode root) {
d(root);
return ans;
}
}
typedef struct {
char* key;
int val;
int i;
UT_hash_handle hh;
} HashItem;
int d(struct TreeNode* n, HashItem** h, int* i, struct TreeNode** ans, int* pos) {
if (n == NULL) return 0;
char* s = malloc(sizeof(char) * 32);
sprintf(s, "%d,%d,%d", n->val, d(n->left, h, i, ans, pos), d(n->right, h, i, ans, pos));
HashItem* pEntry = NULL;
HASH_FIND_STR(*h, s, pEntry);
if (pEntry == NULL) {
pEntry = malloc(sizeof(HashItem));
pEntry->key = s;
pEntry->val = 0;
pEntry->i = ++*i;
HASH_ADD_STR(*h, key, pEntry);
} else if (pEntry->val == 0) {
pEntry->val = 1;
ans[(*pos)++] = n;
}
return pEntry->i;
}
struct TreeNode** findDuplicateSubtrees(struct TreeNode* root, int* returnSize){
HashItem* h = NULL;
int i = 0, pos = 0;
struct TreeNode** ans = malloc(sizeof(struct TreeNode*) * 1e4);
d(root, &h, &i, ans, &pos);
*returnSize = pos;
free(h);
return ans;
}
class Solution {
private:
unordered_map<string, pair<int, int>> h;
vector<TreeNode*> ans;
int i = 0;
string d(TreeNode* n) {
if (n == nullptr) return "0";
string s = to_string(n->val) + "," + d(n->left) + "," + d(n->right);
if (h.find(s) == h.end()) h.emplace(s, pair{++i, 0});
else if (h[s].second == 0) {
h[s].second = 1;
ans.emplace_back(n);
}
return to_string(h[s].first);
}
public:
vector<TreeNode*> findDuplicateSubtrees(TreeNode* root) {
return d(root), ans;
}
};
class Solution:
def d(self, n: Optional[TreeNode]) -> str: # 字符串实现
if n == None: return '0'
s = str(n.val) + ',' + self.d(n.left) + ',' + self.d(n.right)
if s not in self.h:
self.i += 1
self.h[s] = [self.i, 0]
elif self.h[s][1] == 0:
self.h[s][1] = 1
self.ans.append(n)
return str(self.h[s][0])
def findDuplicateSubtrees(self, root: Optional[TreeNode]) -> List[Optional[TreeNode]]:
self.h, self.i, self.ans = dict(), 0, []
self.d(root)
return self.ans
class Solution:
def d(self, n: Optional[TreeNode]) -> int: # 元组实现
if n == None: return 0
s = (n.val, self.d(n.left), self.d(n.right))
if s not in self.h:
self.i += 1
self.h[s] = [self.i, 0]
elif self.h[s][1] == 0:
self.h[s][1] = 1
self.ans.append(n)
return self.h[s][0]
def findDuplicateSubtrees(self, root: Optional[TreeNode]) -> List[Optional[TreeNode]]:
self.h, self.i, self.ans = dict(), 0, []
self.d(root)
return self.ans
var findDuplicateSubtrees = function(root) {
const stack = [], is = new Map, h = new Map, ans = []
let p = root, prev = null, i = 0
while (stack.length || p) {
while (p) {
stack.push(p)
p = p.left
}
const n = stack.pop()
if (n.right === null || n.right === prev) {
const s = n.val + ',' + is.get(n.left) + ',' + is.get(n.right)
if (h.has(s) === false) {
h.set(s, [i++, 0])
} else if (h.get(s)[1] === 0) {
ans.push(n)
h.get(s)[1] = 1
}
is.set(n, h.get(s)[0])
prev = n
} else {
stack.push(n)
p = n.right
}
}
return ans
};
function findDuplicateSubtrees(root: TreeNode | null): Array<TreeNode | null> {
const stack = [], ans = [], is = new Map, h = new Map
let p = root, prev = null, i = 0
while (stack.length || p) {
while (p) {
stack.push(p)
p = p.left
}
const n = stack.pop()
if (n.right === null || n.right === prev) {
const s = n.val + ',' + is.get(n.left) + ',' + is.get(n.right)
if (h.has(s) === false) {
h.set(s, [i++, 0])
} else if (h.get(s)[1] === 0) {
ans.push(n)
h.get(s)[1] = 1
}
is.set(n, h.get(s)[0])
prev = n
} else {
stack.push(n)
p = n.right
}
}
return ans
};
class Solution {
function findDuplicateSubtrees($root) {
$stack = array();
$ans = array();
$h = array();
$i = 0;
$p = $root;
$prev = null;
while (count($stack) || $p) {
while ($p) {
$stack []= $p;
$p = $p->left;
}
$n = array_pop($stack);
if ($n->right === null || $n->right === $prev) {
$s = $n->val . ',' . $n->left->i . ',' . $n->right->i;
if ($h[$s] === null) {
$h[$s] = array(++$i, 0);
} elseif ($h[$s][1] === 0) {
$h[$s][1] = 1;
$ans []= $n;
}
$n->i = $h[$s][0];
$prev = $n;
} else {
$stack []= $n;
$p = $n->right;
}
}
return $ans;
}
}
func findDuplicateSubtrees(root *TreeNode) []*TreeNode {
var prev *TreeNode
i, p, stack, ans, is, h := 0, root, []*TreeNode{}, []*TreeNode{}, map[*TreeNode]int{}, map[[3]int][2]int{}
for len(stack) > 0 || p != nil {
for p != nil {
stack = append(stack, p)
p = p.Left
}
n := stack[len(stack) - 1]
stack = stack[:len(stack) - 1]
if n.Right == nil || n.Right == prev {
s := [3]int{n.Val, is[n.Left], is[n.Right]}
if _, ok := h[s]; ok == false {
i++
h[s] = [2]int{i, 0}
} else if (h[s][1] == 0) {
ans = append(ans, n)
h[s] = [2]int{h[s][0], 1}
}
is[n] = h[s][0]
prev = n
} else {
stack = append(stack, n)
p = n.Right
}
}
return ans
}
class Solution {
public List<TreeNode> findDuplicateSubtrees(TreeNode root) {
List<TreeNode> ans = new ArrayList<TreeNode>();
Map<TreeNode, Integer> is = new HashMap<TreeNode, Integer>();
Map<String, int[]> h = new HashMap<String, int[]>();
Deque<TreeNode> stack = new ArrayDeque<TreeNode>();
TreeNode p = root, prev = null;
int i = 0;
while (stack.isEmpty() == false || p != null) {
while (p != null) {
stack.push(p);
p = p.left;
}
TreeNode n = stack.pop();
if (n.right == null || n.right == prev) {
String s = n.val + "," + is.get(n.left) + "," + is.get(n.right);
if (h.containsKey(s) == false) {
i++;
h.put(s, new int[]{i, 0});
} else if (h.get(s)[1] == 0) {
ans.add(n);
h.get(s)[1] = 1;
}
is.put(n, h.get(s)[0]);
prev = n;
} else {
stack.push(n);
p = n.right;
}
}
return ans;
}
}
public class Solution {
public IList<TreeNode> FindDuplicateSubtrees(TreeNode root) {
List<TreeNode> ans = new List<TreeNode>();
Stack<TreeNode> stack = new Stack<TreeNode>();
TreeNode p = root, prev = null;
Dictionary<TreeNode, int> d = new Dictionary<TreeNode, int>();
Dictionary<string, int[]> h = new Dictionary<string, int[]>();
int i = 0;
while (stack.Count > 0 || p != null) {
while (p != null) {
stack.Push(p);
p = p.left;
}
TreeNode n = stack.Pop();
if (n.right == null || n.right == prev) {
string s = n.val + "," + (n.left != null ? d[n.left] : "") + "," + (n.right != null ? d[n.right] : "");
if (h.ContainsKey(s) == false) {
h.Add(s, new int[2]{i++, 0});
} else if (h[s][1] == 0) {
ans.Add(n);
h[s][1] = 1;
}
d.Add(n, h[s][0]);
prev = n;
} else {
stack.Push(n);
p = n.right;
}
}
return ans;
}
}
typedef struct {
char* key;
int val;
int i;
UT_hash_handle hh;
} HashItem;
typedef struct {
struct TreeNode* key;
int i;
UT_hash_handle hh;
} HashTreeNode;
struct TreeNode** findDuplicateSubtrees(struct TreeNode* root, int* returnSize){
struct TreeNode** stack = malloc(sizeof(struct TreeNode*) * 1e4);
int pos = 0, i = 0, j = 0;
struct TreeNode* p = root;
struct TreeNode* prev = NULL;
HashItem* h = NULL;
HashTreeNode* is = NULL;
struct TreeNode** ans = malloc(sizeof(struct TreeNode*) * 1e4);
while (pos || p) {
while (p) {
stack[pos++] = p;
p = p->left;
}
struct TreeNode* n = stack[--pos];
if (n->right == NULL || n->right == prev) {
HashTreeNode* pNodeEntry = NULL;
HASH_FIND_INT(is, &n->left, pNodeEntry);
int l = pNodeEntry ? pNodeEntry->i : 0;
HASH_FIND_INT(is, &n->right, pNodeEntry);
char* s = malloc(sizeof(char) * 17);
sprintf(s, "%d,%d,%d", n->val, l, pNodeEntry ? pNodeEntry->i : 0);
HashItem* pEntry = NULL;
HASH_FIND_STR(h, s, pEntry);
if (pEntry == NULL) {
pEntry = malloc(sizeof(HashItem));
pEntry->key = s;
pEntry->val = 0;
pEntry->i = ++i;
HASH_ADD_STR(h, key, pEntry);
} else if (pEntry->val == 0) {
pEntry->val = 1;
ans[j++] = n;
}
pNodeEntry = malloc(sizeof(HashTreeNode));
pNodeEntry->key = n;
pNodeEntry->i = pEntry->i;
HASH_ADD_INT(is, key, pNodeEntry);
prev = n;
} else {
stack[pos++] = n;
p = n->right;
}
}
free(h);
free(is);
free(stack);
free(p);
free(prev);
*returnSize = j;
return ans;
}
class Solution {
public:
vector<TreeNode*> findDuplicateSubtrees(TreeNode* root) {
stack<TreeNode*> st;
TreeNode* p = root;
TreeNode* prev = nullptr;
unordered_map<string, vector<int>> h;
unordered_map<TreeNode*, string> is;
int i = 0;
vector<TreeNode*> ans;
while (st.empty() == false || p) {
while (p) {
st.push(p);
p = p->left;
}
TreeNode* n = st.top();
st.pop();
if (n->right == nullptr || n->right == prev) {
string s = to_string(n->val) + "," + is[n->left] + "," + is[n->right];
if (h.find(s) == h.end()) h.emplace(s, vector<int>{i++, 0});
else if (h[s][1] == 0) {
h[s][1] = 1;
ans.emplace_back(n);
}
is.emplace(n, to_string(h[s][0]));
prev = n;
} else {
st.push(n);
p = n->right;
}
}
return ans;
}
};
class Solution:
def findDuplicateSubtrees(self, root: Optional[TreeNode]) -> List[Optional[TreeNode]]: # 字符串实现
stack, h, d, p, prev, i, ans = [], {}, {}, root, None, 0, []
while len(stack) or p:
while p:
stack.append(p)
p = p.left
n = stack.pop()
if n.right == None or n.right == prev:
s = str(n.val) + ',' + (d[n.left] if n.left else '') + ',' + (d[n.right] if n.right else '')
if s not in h:
i += 1
h[s] = [i, 0]
elif h[s][1] == 0:
h[s][1] = 1
ans.append(n)
d[n] = str(h[s][0])
prev = n
else:
stack.append(n)
p = n.right
return ans
class Solution:
def findDuplicateSubtrees(self, root: Optional[TreeNode]) -> List[Optional[TreeNode]]: # 元组实现
stack, h, d, p, prev, i, ans = [], {}, {}, root, None, 0, []
while len(stack) or p:
while p:
stack.append(p)
p = p.left
n = stack.pop()
if n.right == None or n.right == prev:
s = (n.val, d[n.left] if n.left else None, d[n.right] if n.right else None)
if s not in h:
i += 1
h[s] = [i, 0]
elif h[s][1] == 0:
h[s][1] = 1
ans.append(n)
d[n] = h[s][0]
prev = n
else:
stack.append(n)
p = n.right
return ans