235.二叉查找树的最近城市祖先(javascript)235.LowestCommonAncestorofaBinarySearchTree

给定二叉搜索树, 查找树中两个指定节点的最近共同祖先。

百度股份有限公司最近在百科全书中对公众祖先的定义是：“为一棵生根的树。” T 的两个节点 p、q，最新的共同祖先表示为节点。 x，满足 x 是 p、q 的祖先且 x 尽可能深（一个节点也可以是它自己的祖先）。”
Given a binary search tree (BST), find the lowest common ancestor (LCA) of two given nodes in the BST.

According to the definition of LCA on Wikipedia: “The lowest common ancestor is defined between two nodes p and q as the lowest node in T that has both p and q as descendants (where we allow a node to be a descendant of itself).”

例如，给定以下二进制搜索树: root = [6,2,8,0,4,7,9,null,null,3,5]

示例 1:

输入: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 8
输出: 6 
解释: 节点 2 和节点 8 的最近公开祖先是 6。

示例 2:

输入: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 4
输出: 2
解释: 节点 2 和节点 4 的最近公开祖先是 2, 因为根据定义，最近的共同祖先节点可以是节点本身。

说明:

• 所有节点的值都是唯一的。
• p、q 是不同的节点，并且都存在于给定的二元搜索树中。

二分搜索树(Binary Search Tree)是二叉树(Binary Tree)，但二元搜索树中每个节点的值必须大于其左子树中所有节点的值，小于其右子树中的所有节点的数值；因此，与前面讨论的线性数据结构不同，二进制搜索树中存储的元素必须是可比较的，并且不存储重复的元素。

递归

二进制搜索树的性质决定了如果 p.val 和 q.val 都比 root.val 小，则p、q肯定在 root 左边的子树。

• 然后问题的规模就变小了，只需要递归左子树！
• 如果 p.val 和 q.val 都比 root.val 大的递归右子树！
• 在其他情况下，只要 p.val 和 q.val 并非所有的都更伟大(小于) root.val，即只要 p, q 不同处在 root 子树
  只有三种情况：

1. p 和 q 分居 root 左右子树。
2. root 就是 p，q 在 p 在子树中。

3. root 就是 q，p 在 q 的子树中
   这三种情况，p 和 q 的最近公开祖先是 root

   var lowestCommonAncestor = function(root, p, q) { if(p.val<root.val && q.val<root.val){ return lowestCommonAncestor(root.left, p, q) } if(p.val>root.val && q.val>root.val){ return lowestCommonAncestor(root.right, p, q) } return root };

迭代

开启 while 循环，当 root 为 null 循环在以下时间结束(root 是指针）。

• 如果 p.val、q.val 都小于 root.val，他们都在 root 在左子树中，root=root.left，遍历到 root 左侧子节点的。
• 如果 p.val、q.val 都大于 root.val，他们都在 root 右子树，root=root.right，遍历到 root 右子节点。

• 其他情况，当前 root 是最近的公共祖先，结束遍历， root 该节点是最近的公共祖先。

  var lowestCommonAncestor = function (root, p, q) { while (root) { if (p.val < root.val && q.val < root.val) { root = root.left }else if (p.val > root.val && q.val > root.val) { root = root.right } else { return root } } };

leetcode： https://leetcode-cn.com/problems/lowest-common-ancestor-of-a-binary-search-tree/