写点什么

LeetCode 题解:236. 二叉树的最近公共祖先,递归,JavaScript,详细注释

用户头像
Lee Chen
关注
发布于: 2021 年 01 月 11 日

原题链接:https://leetcode-cn.com/problems/lowest-common-ancestor-of-a-binary-tree/


解题思路:


  1. 使用递归遍历所有节点,如果一个节点的左右子树中同时含有 p 和 q,则它就是最近公共祖先。

  2. 递归终止条件有两种:

* 如果当前节点是 p 或 q,则将其返回。

* 如果当前节点为空,则退出循环。

  1. 递归分别下探到左右子节点,同时获取他们的返回值,返回值存在两种情况:

* 如果返回值同时含有 p 和 q,表示当前节点为公共祖先,则将其返回。由于第一次遇到公共祖先后,就会将其返回,其上层的递归不会在遇到 p 货 q,那么这个节点必然为最近公共祖先。

* 如果返回值不同时含有 p 或 q,则将其中之一返回给上层递归判断。如果 p 或 q 自身就是最近公共祖先,其自身就会不断被返回,成为递归的最终结果。


/** * Definition for a binary tree node. * function TreeNode(val) { *     this.val = val; *     this.left = this.right = null; * } *//** * @param {TreeNode} root * @param {TreeNode} p * @param {TreeNode} q * @return {TreeNode} */var lowestCommonAncestor = function (root, p, q) {  // 如果root不存在,直接退出循环  // 如果查询到p或q,则将其返回,供上层递归判断  if (!root || root === p || root === q) {    return root;  }
// 获取在子树中匹配到的p和q节点 const left = lowestCommonAncestor(root.left, p, q); const right = lowestCommonAncestor(root.right, p, q);
// 如果p和q同时匹配到,当前节点即为最近公共祖先 if (left && right) { return root; }
// 如果没有同时匹配到p和q,就将匹配到的节点返回给上层判断 // 最近公共祖先是其本身的情况,会通过该步骤返回 return left || right;};
复制代码


发布于: 2021 年 01 月 11 日阅读数: 22
用户头像

Lee Chen

关注

还未添加个人签名 2018.08.29 加入

还未添加个人简介

评论

发布
暂无评论
LeetCode题解:236. 二叉树的最近公共祖先,递归,JavaScript,详细注释