c#二叉树的最近公共祖先如何找

   2024-10-05 4580
核心提示:在C#中,我们可以通过递归的方法来找到二叉树中两个节点的最近公共祖先。具体步骤如下:定义一个递归函数,该函数的作用是在以ro

在C#中,我们可以通过递归的方法来找到二叉树中两个节点的最近公共祖先。具体步骤如下:

定义一个递归函数,该函数的作用是在以root为根节点的二叉树中查找节点p和节点q的最近公共祖先。如果root为null,表示当前节点为空,直接返回null。如果root等于p或q,表示当前节点就是要查找的节点之一,直接返回当前节点。递归查找root的左子树和右子树,分别得到left和right。如果left和right均不为空,说明p和q分别位于root的左右子树,那么root就是它们的最近公共祖先。如果left为空而right不为空,说明p和q都在右子树中,返回right。如果left不为空而right为空,说明p和q都在左子树中,返回left。如果left和right均为空,说明p和q都不在root的子树中,返回null。

下面是C#代码实现:

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) {        return root;    } else if(left != null) {        return left;    } else {        return right;    }}

在代码中,TreeNode表示二叉树的节点,包含左右子树和值等属性。我们调用LowestCommonAncestor函数,传入树的根节点root以及要查找的两个节点p和q,即可找到它们的最近公共祖先。

 
举报打赏
 
更多>同类物流大全
推荐图文
推荐物流大全
点击排行

网站首页  |  关于我们  |  联系方式 | 网站留言    |  赣ICP备2021007278号