二叉树中两个点的最低公共祖先

一个二叉树根节点root，两个点A和B

  • 情况1，这是一个排序的二叉树
    • 从树的根节点出发，当前节点如果同时大于A和B，则到左子树找
    • 从树的根节点出发，当前节点如果同时小于A和B，则到右子树找
    • 如果当前节点，比一个大，比一个小，那么这就是所求的最低公共祖先
  • 情况2，不是排序的二叉树，但是每个节点有父节点的指针
    • 从两个节点A和B出发，一直找父节点，形成两个链表
    • 转变成求两个链表的公共节点问题
  • 情况3，不是排序的，也没有父指针
    • 从根节点遍历树，记录下从根节点到A和B的路径(可以用栈)
    • 两个栈，记录了路径，最后找一下公共节点即可