day18| 二叉树

三道题目 众数，最小差和公共祖先。

众数和最小差的逻辑类似，都是利用 BFS 的中序遍历是有序的，因此在遍历过程中可以利用有序的特性减少复杂度。

以最小差为例

      # 二叉树 中序是有序的  我们在中序查找每个最小差值即可
        while cur or stack:
            while cur:
                stack.append(cur)
                cur=cur.left
            cur = stack.pop()
            if pre:
                mindiff = min(abs(pre.val-cur.val),mindiff)
            pre = cur
            cur = cur.right
        return mindiff

公共祖先则是要数清楚祖先的情况，

• p,q分别在左右子树，需要向上返回cur
• p,q在一边子树，此时只用返回最上面的那层节点。

整体的逻辑就是 当我们的 cur 遍历到p和 q 时直接向上返回(因为必然在 cur 为根，且 cur 为p或 q的树的下面)

如果cur左右子树是发现左右存在p和 q，则返回 cur

如果只发现一个 p ，则直接返回 p (相当于把 cur 给替代了，他们公共祖先的情况是一致的)