树

二叉树对称性递归

对称性递归对一个对称的数据结构从整体的对称性思考，把大问题分解成子问题进行递归

需要构造辅助函数：

通常只用根节点子树对称性无法完全解决问题，必须要用到子树的某一部分进行递归，即要调用辅助函数比较两个部分子树。形式上主函数参数列表只有一个根节点，辅助函数参数列表有两个节点

模板之递归结束条件：特殊情况判断

如果是单树问题，一般来说只要进行以下判断：

if !root {
	return true/false
}
if !root.Left {
	return true/false/递归函数
}
if !root.Right {
	return true/false/递归函数
}

如果是双树问题(根节点分别为p,q)，一般来说进行以下判断：

if !p && !q {
	return true/false
}
if !p || !q {
	return true/false
}

模板之返回值

通常对称性递归的返回值是多个条件的复合判断语句，可能是以下几种条件判断的组合：

• 节点非空的判断
• 节点值比较判断
• (单树)调用根节点左右子树的递归函数进行递归判断
• (双树)调用两棵树的左右子树的递归函数进行判断

100. 相同的树

特殊判断：如果两棵树都是空树那么必然相同；如果两棵树其中只有一棵树为空树那么必不相同

返回值：两棵树都非空+根节点值相同+左子树相同+右子树相同

func isSameTree(p *TreeNode, q *TreeNode) bool {
    if p == nil && q == nil {
        return true
    }
    return p != nil && q != nil && p.Val == q.Val &&
        isSameTree(p.Left, q.Left) && isSameTree(p.Right, q.Right)
}