温馨提示×

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

c#
小樊
83
2024-07-26 02:40:16
栏目: 编程语言

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

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

0