[数据结构与算法]力扣235和236 二叉树的最近公共祖先问题

236. 二叉树的最近公共祖先 - 力扣（LeetCode）

• 二叉树查找最近公共祖先

  • 普通二叉树从底向上查找，后续遍历是天然的回溯
  • 递归三部曲：
    • 1.确认递归函数返回值和参数
      • 需要返回是否是目标结点，首先考虑到返回布尔值；
      • 如果找到了目标结点也可以直接返回目标节点，则可以通过返回的结点是否为空来判断是否找到了目标结点。
      • 参数：下一个结点，目标结点1 ，目标结点2
    • 2.确认结束条件：
      • 若当前结点为空，则返回空；
      • 若当前结点不为目标结点，则返回空；
      • 若当前结点为目标结点，则返回该目标结点；
    • 确认单层递归逻辑（达到对应条件返回对应的值）
      • 根据每个左右结点的返回值进行判断
      • 1.左右结点返回值都不为空，则当前结点为最近公共祖先
      • 2.若左结点为空，右结点不为空，返回右结点值
      • 3.若右结点为空，左结点不为空，返回左结点值
      • 4.若都为空，则返回空

代码：

// 后续遍历是天然的回溯：从树的底层向上寻找
var lowestCommonAncestor = function (root, p, q) {
    // 使用递归的方法
    // 需要从下到上，所以使用后序遍历
    // 1. 确定递归的函数
    const travelTree = function (root, p, q) {
        // 2. 确定递归终止条件
        if (root === null || root === p || root === q) {
            return root;
        }
        // 3. 确定递归单层逻辑
        let left = travelTree(root.left, p, q);
        let right = travelTree(root.right, p, q);
        if (left != null && right != null) return root;
        if (left == null && right != null) {
            return right;
        } else if (left != null && right == null) {
            return left;
        } else { //  (left == null && right == null)
            return null;
        }
    }
    return travelTree(root, p, q);
};

?235. 二叉搜索树的最近公共祖先 - 力扣（LeetCode）

• 二叉搜索树的最近公共祖先

  • 二叉搜索树是有序的，根结点的左子树都比根结点小，根结点的右子树都比根结点大
  • 利用二叉搜索树有序的特性，从上到下遍历二叉搜索树
  • 从上到下的遍历：因为本题是没有中间结点的处理逻辑的，所以采用哪种遍历顺序都无所谓
  • 通过当前结点的值是否在目标结点区间去判断该结点是否为最近公共祖先
    • 1.若当前结点的值比俩个目标结点的值都小，就要往右子树找
    • 2.若当前结点的值比俩个目标结点的值都大，就要往左子树找
    • 3.当前结点的值在俩个目标结点的中间，则该结点为最近公共祖先
    • 4.如果当前结点为空 返回空

代码：

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

?

?