这篇文章将为大家详细讲解有关python二叉树的最近公共祖先如何理解，文章内容质量较高，因此小编分享给大家做个参考，希望大家阅读完这篇文章后对相关知识有一定的了解。给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。百度百科中最近公共祖先的定义为：“对于有根树 T 的两个结点 p、q，最近公共祖先表示为一个结点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”例如，给定如下二叉树: root =[3,5,1,6,2,0,8,null,null,7,4]示例 1:输入: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1 输出: 3 解释: 节点 5 和节点 1 的最近公共祖先是节点 3。
示例2:答案：
解析：
通过递归的方式，分别从他的左右两个子节点往下找，如果都不为空，说明他们最近的公共祖先节点肯定是当前root节点，如果有一个为空，说明他们最近的公共祖先节点在另一个在子节点上。这种解法和DFS很像，先从最左端的叶子节点开始找起，然后再网上回溯，下面再来看一种解法
Map中key记录的是当前节点，value记录的是当前节点的父节点，第一个while循环使用的是DFS，直到找到p和q节点为止，第二个while循环会把p节点以及他的的父节点，以及父节点的父节点……都加入到ancestors集合中，第3个while循环不断的取出q节点和他的父节点以及父节点的父节点……直到在ancestors中能找到为止，找到的那个正好即是p的祖先节点也同时是q的祖先节点，同时也是最近的。关于python二叉树的最近公共祖先如何理解就分享到这里了，希望以上内容可以对大家有一定的帮助，可以学到更多知识。如果觉得文章不错，可以把它分享 香港云主机出去让更多的人看到。
这篇文章主要介绍“java Arrays排序如何使用”的相关知识，小编通过实际案例向大家展示操作过程，操作方法简单快捷，实用性强，希望这篇“java Arrays排序如何使用”文章能帮助大家解决问题。1.Arrays.sort(int[] a)这种形式是对一个…
免责声明：本站发布的图片视频文字，以转载和分享为主，文章观点不代表本站立场，本站不承担相关法律责任；如果涉及侵权请联系邮箱：360163164@qq.com举报，并提供相关证据，经查实将立刻删除涉嫌侵权内容。
微信扫一扫 
