如果一个节点X，它左树结构和右树结构完全一样，那么我们说以X为头的树是相等树。给定一棵二叉树的头节点head，返回head整棵树上有多少棵相等子树。
方法一：自然智慧。
递归函数：头num=左num+右num+0或1。
相等判断函数：左结构=右结构，O(N)。
树越不平衡，复杂度越低，因此算复杂度的时候，只需要考虑平衡树。
master公式：T(N)=2T(N/2)+O(N)。2T(N/2)是递归。O(N)是相等判断函数。
根据master公式，时间复杂度是O(N*logN)。
方法二：方法一的相等判断函数用哈希函数。
递归函数：头num=左num+右num+0或1。头哈希=【左哈希+头值+右哈希】的哈希值。这个递归有两个返回值。
相等判断函数：左结构=右结构，用哈希值判断，O(1)。
树越不平衡，复杂度越低，因此算复杂度的时候，只需要考虑平衡树。
master公式：T(N)=2T(N/2)+O(1)。2T(N/2)是递归。O(1)是相等判断函数。
根据master公式，时间复杂度是O(N)。
代码用golang编写。代码如下：
package main
import (
"crypto/md5"
"fmt"
)
func main() {
head := &Node{Val: 1}
head.Left = &Node{Val: 2}
head.Right = &Node{Val: 2}
head.Left.Left = &Node{Val: 3}
head.Left.Right = &Node{Val: 4}
head.Right.Left = &Node{Val: 3}
head.Right.Right = &Node{Val: 4}
ret1 := sameNumber1(head)
fmt.Println(ret1)
ret2 := sameNumber2(head)
fmt.Println(ret2)
}
type Node struct {
Val int
Left *Node
Right *Node
}
// 方法一：时间复杂度O(N * logN)
func sameNumber1(head *Node) int {
if head == nil {
return 0
}
return sameNumber1(head.Left) + sameNumber1(head.Right) + twoSelectOne(same(head.Left, head.Right), 1, 0)
}
func same(left *Node, right *Node) bool {
if left == nil && right == nil {
return true
}
if left == nil || right == nil {
return false
}
// 两个都不为空
return left.Val == right.Val && same(left.Left, right.Left) && same(left.Right, right.Right)
}
func twoSelectOne(c bool, a int, b int) int {
if c {
return a
} else {
return b
}
}
type Info struct {
ans int
str string
}
//方法二
func sameNumber2(head *Node) int {
return process2(head).ans
}
func process2(head *Node) *Info {
if head == nil {
return &Info{ans: 0, str: fmt.Sprintf("%x", md5.Sum([]byte("#,")))}
}
l := process2(head.Left)
r := process2(head.Right)
ans := twoSelectOne(l.str == r.str, 1, 0) + l.ans + r.ans
str := fmt.Sprintf("%x", md5.Sum([]byte(fmt.Sprintf("%d,%s%s", head.Val, l.str, r.str))))
return &Info{ans: ans, str: str}
}执行结果如下：
