相同的树：结构和值必须一起过
同一位置两边都空才算对齐，一边空就否；都在还要值相等，再同步比左对左、右对右。只比值或只比形状都不够。
isSameTree(p, q)：都空为真；恰好一个空为假；值不等为假；否则同侧递归左对左、右对右，两边都真才真。结构缺口和值缺口任意一个都能否决。时间 O(min(m,n))，空间 O(h)。
给你两棵二叉树的根 p 和 q，判断它们是否相同。相同只有一句话：对应位置的结构一样，并且对应节点的值一样。少一边孩子、多一边孩子、值对不上，都算不同。
主例两边都是 [1, 2, 3]：根 1 对 1，左 2 对 2，右 3 对 3，三对都在且值相等，返回 true。
只扫一层值、或只看「两边是不是都有左右孩子」，都会漏。本文要回答：空节点为什么必须纳入比较，以及同侧配对和对称树的异侧配对差在哪。
一对节点同时问结构和值
两棵树是否相同，可以收成对每一对对应节点的提问。p、q 都空：这个位置两边都没有节点，结构对齐，这一对相同。恰好一个空：一边有节点、一边是缺口，结构已经不同，整棵否决。两边都在：先比值，值不等整棵否决；值相等，再问左孩子那一对、右孩子那一对，两问都真才真。
缺的不是「根相不相等」这一张成绩单，而是把空当成一等公民。主例若改成 p=[1,2]、q=[1,null,2]，根都是 1，值对得上；p 的左是 2、右是空，q 的左是空、右是 2。只比值会误判相同，只数节点个数也会误判。必须在「2 对空」「空对 2」这两步立刻返回 false。
值的缺口同样单独否决。p=[1,2,3]、q=[1,2,4]，结构完全一样，右孩子 3 对 4 值不等，整棵不同。所以递归里空判断和值判断都要写，而且都要写在继续下探之前。先读 p.Val 再判断 p 是否为空，空指针会炸。
配对方向是同侧：p.Left 对 q.Left，p.Right 对 q.Right。这和对称树相反——那边比的是 p.Left 对 q.Right。主例三对都是同侧：下标 (0,0)、(1,1)、(2,2)。若把主例的 q 左右对调成 [1,3,2]，同侧比较会在 2 对 3 处失败，尽管两棵树像镜子。题目要的是相同，不是对称。
用手走主例。第一对根：1 和 1 都在且相等。第二对左：2 和 2 都在且相等。第三对右：3 和 3 都在且相等。左右再往下都是空对空，返回 true。演示四帧标的就是这三对通过、最后收 true。一边已经判明不同，另一边不必再走完，时间按较短那棵的节点数封顶。
同侧不是镜像相同比左对左、右对右；对称比左对右、右对左。空对空是结构对齐，空对非空是结构缺口，两者不能省。
Go：递归同步遍历
func isSameTree(p, q *TreeNode) bool {if p == nil && q == nil { return true }if p == nil || q == nil { return false }if p.Val != q.Val { return false }return isSameTree(p.Left, q.Left) &&isSameTree(p.Right, q.Right)}
1都空：这个位置结构对齐。
2恰好一个空：结构缺口，整棵不同。必须写在读 Val 之前。
3值不等：值缺口，整棵不同。
4同侧继续：左对左、右对右，两问都真才真。
总结
同一位置：结构先对齐，值再相等，然后左对左、右对右。主例三对都过，true。
- 空对空是对齐，空对非空是不同。[1,2] 和 [1,null,2] 值像，结构否。
- 结构过了还要比值。[1,2,3] 和 [1,2,4] 形状同，右孩子否。
- 配对是同侧。对称树才是异侧，不能混。