淘宝上的网站建设可信,公司网站推广的方法,报名工具小程序官网,wordpress能不能做商城最近公共祖先
问题描述
给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。百度百科中最近公共祖先的定义为#xff1a;“对于有根树 T 的两个节点 p、q#xff0c;最近公共祖先表示为一个节点 x#xff0c;满足 x 是 p、q 的祖先且 x 的深度尽可能大#xff08;一…最近公共祖先
问题描述
给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。百度百科中最近公共祖先的定义为“对于有根树 T 的两个节点 p、q最近公共祖先表示为一个节点 x满足 x 是 p、q 的祖先且 x 的深度尽可能大一个节点也可以是它自己的祖先。”详见leetcode236
问题分析
按照前序遍历的顺序遍历二叉树对于遍历到的当前节点root判断其与要寻找公共祖先的两个节点p和q的关系,如果rootp或者rootq则root是p和q的最近公共祖先否则在root的左右子树分别寻找p和q如果p和q在root的左子树和右子树则root是p和q的最近公共祖先如果p和q均在root的左子树或者右子树则在root的左子树或者右子树继续递归寻找最近公共祖先
代码实现
private TreeNode res null;
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {dfs(root,p,q);return res;
}public boolean dfs(TreeNode root, TreeNode p,TreeNode q){if(rootnull){return false;}boolean left dfs(root.left,p,q);boolean right dfs(root.right,p,q);if(leftright){res root;}if(root p || root q){res root;}return left || right || rootp || rootq;
}
