在线修图网站,自助建站免费建站五个平台,成都必去的十大景点,WordPress 左边导航数据结构——二叉树的公共祖先问题 236. 二叉树的最近公共祖先思路 235. 二叉搜索树的最近公共祖先思路1.递归2.迭代 236. 二叉树的最近公共祖先
236. 二叉树的最近公共祖先
给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。
百度百科中最近公共祖先的定义为#x… 数据结构——二叉树的公共祖先问题 236. 二叉树的最近公共祖先思路 235. 二叉搜索树的最近公共祖先思路1.递归2.迭代 236. 二叉树的最近公共祖先
236. 二叉树的最近公共祖先
给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。
百度百科中最近公共祖先的定义为“对于有根树 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 [3,5,1,6,2,0,8,null,null,7,4], p 5, q 4 输出: 5 解释: 节点 5 和节点 4 的最近公共祖先是节点 5。因为根据定义最近公共祖先节点可以为节点本身。
说明:
所有节点的值都是唯一的。 p、q 为不同节点且均存在于给定的二叉树中。
思路
1、二叉树如果能自底向上查找就可以找到公共祖先。自底向上查找需要利用回溯后序遍历就是天然的回溯过程最先处理的一定是叶子节点。
2、判断一个节点是节点q和节点p的公共公共祖先如果找到一个节点发现左子树出现结点p右子树出现节点q或者 左子树出现结点q右子树出现节点p那么该节点就是节点p和q的最近公共祖先。
递归函数返回值以及参数要返回最近公共节点返回值是TreeNode 如果遇到p或者q就把q或者p返回返回值不为空就说明找到了q或者p。终止条件如果找到了 节点p或者q或者遇到空节点就返回。单层递归逻辑 本题函数有返回值是因为回溯的过程需要递归函数的返回值做判断但本题我们依然要遍历树的所有节点。 要遍历整棵树是因为后序遍历中如果想利用left和right做逻辑处理 不能立刻返回而是要等left与right逻辑处理完之后才能返回。所以即使在左子树中找到了p和q仍要等right遍历完右子树。 用left和right接住左子树和右子树的返回值 如果left 和 right都不为空说明此时root就是最近公共节点。 如果left为空right不为空就返回right说明目标节点是通过right返回的反之依然。 图中节点10的左子树返回null右子树返回目标值7那么此时节点10的处理逻辑就是把右子树的返回值最近公共祖先7返回上去左子树的返回值空被舍弃。最终结果被传至根节点。 如果left和right都为空则返回left或者right都是可以的也就是返回空。
代码随想录完整流程图 时间复杂度 O ( n ) O(n) O(n) 空间复杂度 O ( n ) O(n) O(n)
class Solution {public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {if (root null || root p || root q) return root;// 后序遍历TreeNode left lowestCommonAncestor(root.left, p, q);TreeNode right lowestCommonAncestor(root.right, p, q);if(left null right null) { // 若未找到节点 p 或 qreturn null;}else if(left null right ! null) { // 若找到一个节点return right;}else if(left ! null right null) { // 若找到一个节点return left;}else { // 若找到两个节点return root;}}
}总结
在递归函数有返回值的情况下
如果要搜索一条边递归函数返回值不为空的时候立刻返回如果搜索整个树直接用一个变量left、right接住返回值这个left、right后序还有逻辑处理的需要也就是后序遍历中处理中间节点的逻辑也是回溯。
搜索一条边的写法
if (递归函数(root.left)) return ;if (递归函数(root.right)) return ;搜索整个树写法
left 递归函数(root.left);
right 递归函数(root.right);
left与right的逻辑处理;
处理后再返回235. 二叉搜索树的最近公共祖先
235. 二叉搜索树的最近公共祖先
给定一个二叉搜索树, 找到该树中两个指定节点的最近公共祖先。
百度百科中最近公共祖先的定义为“对于有根树 T 的两个结点 p、q最近公共祖先表示为一个结点 x满足 x 是 p、q 的祖先且 x 的深度尽可能大一个节点也可以是它自己的祖先。”
例如给定如下二叉搜索树: 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 为不同节点且均存在于给定的二叉搜索树中。
思路
二叉搜索树是有序的因此只要从上到下遍历的时候cur节点是数值在[p, q]区间中则说明该节点cur就是最近公共祖先了。而且不需要遍历整棵树找到结果直接返回即可。
1.递归
递归函数返回值以及参数参数就是当前节点以及两个结点 p、q。 返回值是要返回最近公共祖先所以是TreeNode 。终止条件遇到空返回就可以了。其实都不需要这个终止条件因为题目中说了p、q 为不同节点且均存在于给定的二叉搜索树中。也就是说一定会找到公共祖先的所以并不存在遇到空的情况。单层递归的逻辑在遍历二叉搜索树的时候就是寻找区间[p-val, q-val]注意这里是左闭右闭 那么如果 root-val 大于 p-val同时 root-val 大于q-val那么就应该向左遍历说明目标区间在左子树上。此时不知道p和q谁大所以两个都要判断 如果 root-val 小于 p-val同时 root-val 小于 q-val那么就应该向右遍历目标区间在右子树。 剩下的情况就是cur节点在区间p-val root-val root-val q-val或者 q-val root-val root-val p-val中root就是最近公共祖先了直接返回root。
时间复杂度 O ( n ) O(n) O(n) 空间复杂度 O ( n ) O(n) O(n)
class Solution {public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {if (rootnull) return root; //可不加if (root.valp.val root.valq.val)return lowestCommonAncestor(root.left,p,q);if (root.valp.val root.valq.val)return lowestCommonAncestor(root.right,p,q);return root;}
}2.迭代
利用二叉搜索树的有序性写出简易迭代法
时间复杂度 O ( n ) O(n) O(n) 空间复杂度 O ( 1 ) O(1) O(1)
class Solution {public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {while (true) {if (root.valp.val root.valq.val)root root.left;else if (root.valp.val root.valq.val)root root.right;else break;}return root;}
}
