logo标签列表

在二叉搜索树中找到最近公共祖先

c#binary-tree
4

我有以下代码来查找最近公共祖先（即同时拥有a和b作为后代的最低节点）：

public static Node LCA(Node root, Node a, Node b)
{
    if (root == null)
        return null;

    if (root.IData == a.IData || root.IData == b.IData)
        return root;

    if (root.RightChild != null && (root.RightChild.IData == a.IData || root.RightChild.IData == b.IData))
        return root;

    if (root.LeftChild != null && (root.LeftChild.IData == a.IData || root.LeftChild.IData == b.IData))
        return root;

    if (root.IData > a.IData && root.IData > b.IData)
        return LCA(root.LeftChild, a, b);
    else if (root.IData < a.IData && root.IData < b.IData)
        return LCA(root.RightChild, a, b);
    else
        return root;
}

二叉搜索树是一种数据结构。
                      20
                     /  \
                    8    22
                  /   \
                 4     12 
                      /  \
                    10    14

问题

以下情况会导致失败：

LCA (4, 8) = 20，但应该是8。

LCA (8, 12) = 20，但应该是8。

LCA (8, 23) = 20，参数中有不存在的数字（23）。

您有什么想法吗？

其中Node为：

class Node
{
 public int IData {get; set;}
 public Node RightChild {get; set;}
 public Node LeftChild {get; set;}
}
2
你有没有尝试过“干跑”呢？就是不用电脑，只用铅笔和纸逐步检查你的代码？ - sq33G
1
根据您的定义，输出实际上是正确的。 - st0le
@st0le - 4和8的LCA怎么可能是20？最低的节点（按深度）是8。 - parsh
1
@parsh，我想这取决于你对“后代”的定义有多严格... - st0le
@st0le，如果我有误解，抱歉。我指的是维基百科上的定义——对于两个节点v和w，最近公共祖先被定义为T中同时拥有v和w作为后代的最低节点（我们允许一个节点是其本身的后代）。那么8不是8和12的正确答案吗？ - parsh
显示剩余4条评论
6个回答
1
如果root的IData与a和b都不同，但是root的一个子节点具有与两者之一相同的IData，则返回root，但根据您的定义，如果两个节点在同一子树中，则应返回子节点。由于您还想检查这两个节点是否实际上在树中，因此必须在任何返回之前执行该检查。
public static Node LCA(Node root, Node a, Node b)
{
    if (root == null) return null;
    // what if a == null or b == null ?
    Node small, large, current = root;
    if (a.IData < b.IData)
    {
        small = a;
        large = b;
    }
    else
    {
        small = b;
        large = a;
    }
    if (large.IData < current.IData)
    {
        do
        {
            current = current.LeftChild;
        }while(current != null && large.IData < current.IData);
        if (current == null) return null;
        if (current.IData < small.IData) return LCA(current,small,large);
        // if we get here, current has the same IData as one of the two, the two are
        // in different subtrees, or not both are in the tree
        if (contains(current,small) && contains(current,large)) return current;
        // at least one isn't in the tree, return null
        return null;
    }
    else if (current.IData < small.IData)
    {
        // the symmetric case, too lazy to type it out
    }
    else // Not both in the same subtree
    {
        if (contains(current,small) && contains(current,large)) return current;
    }
    return null; // at least one not in tree
}

public static bool contains(Node root, Node target)
{
    if (root == null) return false;
    if (root.IData == target.IData) return true;
    if (root.IData < target.IData) return contains(root.RightChild,target);
    return contains(root.LeftChild,target);
}
0
2
IData的类型是int，已更新问题与类定义。 - parsh
0

给你:

Console.WriteLine("\n\n /* Lowest Common Ancestor */");
int v1 = 4, v2 = 8;
Node lca = LCA(Root, v1, v2);
Console.WriteLine("LCA of {0} and {1} is: {2}", v1, v2, (lca != null ? lca.Data.ToString() : "No LCA Found"));


public static Node LCA(Node root, int v1, int v2)
{
        if (root == null)
            return null;

        if (root.Data > v1 && root.Data > v2)
            return LCA(root.Left, v1, v2);
        else if (root.Data < v1 && root.Data < v2)
            return LCA(root.Right, v1, v2);
        else
            return root;
}
0

仅供参考，这是查找二叉搜索树公共祖先的C#迭代版本：

public BinaryTreeNode BstLeastCommonAncestor(int e1, int e2)
    {
        //ensure both elements are there in the bst
        var n1 = this.BstFind(e1, throwIfNotFound: true);
        if(e1 == e2)
        {
            return n1;
        }
        this.BstFind(e2, throwIfNotFound: true);
        BinaryTreeNode leastCommonAcncestor = this._root;
        var iterativeNode = this._root;
        while(iterativeNode != null)
        {
            if((iterativeNode.Element > e1 ) && (iterativeNode.Element > e2))
            {
                iterativeNode = iterativeNode.Left;
            }
            else if((iterativeNode.Element < e1) && (iterativeNode.Element < e2))
            {
                iterativeNode = iterativeNode.Right;
            }
            else
            {
                //i.e; either iterative node is equal to e1 or e2 or in between e1 and e2
                return iterativeNode;
            }
        }

Find的定义如下所示

public BinaryTreeNode Find(int e, bool throwIfNotFound)
        {
            var iterativenode = this._root;
            while(iterativenode != null)
            {
                if(iterativenode.Element == e)
                {
                    return iterativenode;
                }
                if(e < iterativenode.Element)
                {
                    iterativenode = iterativenode.Left;
                }
                if(e > iterativenode.Element)
                {
                    iterativenode = iterativenode.Right;
                }
            }
            if(throwIfNotFound)
            {
                throw new Exception(string.Format("Given element {0} is not found", e);
            }
            return null;
        }

而BinaryTreeNode的定义如下：

class BinaryTreeNode
    {
        public int Element;
        public BinaryTreeNode Left;
        public BinaryTreeNode Right;

    }

**测试**

[TestMethod]
        public void LeastCommonAncestorTests()
        {
            int[] a = { 13, 2, 18, 1, 5, 17, 20, 3, 6, 16, 21, 4, 14, 15, 25, 22, 24 };
            int[] b = { 13, 13, 13, 2, 13, 18, 13, 5, 13, 18, 13, 13, 14, 18, 25, 22};
            BinarySearchTree bst = new BinarySearchTree();
            foreach (int e in a)
            {
                bst.Add(e);
                bst.Delete(e);
                bst.Add(e);
            }
            for(int i = 0; i < b.Length; i++)
            {
                var n = bst.BstLeastCommonAncestor(a[i], a[i + 1]);
                Assert.IsTrue(n.Element == b[i]);
            }
        }
0

这是C#版本：

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace LCA
{
    class Node
    {
        public Node(int data, Node a, Node b)
        {
            IData = data;
            LeftChild = a;
            RightChild = b;
        }

        public int IData { get; set; }
        public Node RightChild { get; set; }
        public Node LeftChild { get; set; }
    }

    class Program
    {
        static Node a = new Node(10, null, null);
        static Node b = new Node(14, null, null);
        static Node ab = new Node(12, a, b);
        static Node c = new Node(4, null, null);
        static Node ac = new Node(8, c, ab);
        static Node d = new Node(22, null, null);
        static Node root = new Node(20, ac, d);

        static void Main(string[] args)
        {
            string line;
            line = Console.ReadLine();
            string[] ip = line.Split(' ');
            int ip1 = -1;
            int ip2 = -1;

            if (ip.Length == 2)
            {
                Int32.TryParse(ip[0], out ip1);
                Int32.TryParse(ip[1], out ip2);
                int i = -1;
                Node node = null;
                Node node1 = new Node(ip1, null, null);
                Node node2 = new Node(ip2, null, null);
                if (contains(root, node1))
                {
                    if (!contains(root, node2))
                        node = node1;
                }
                else
                {
                    if (!contains(root, node2))
                        node = new Node(-1, null, null);
                    else
                        node = node2;
                }
                if (node == null)
                    node = LCA(root, node1, node2);

                Int32.TryParse(node.IData.ToString(), out i);

                Console.WriteLine(i);
                Console.ReadLine();
            }
        }

        public static Node LCA(Node root, Node a, Node b)
        {
            if (root == null) return null;

            Node small, large, current = root;
            if (a.IData < b.IData)
            {
                small = a;
                large = b;
            }
            else
            {
                small = b;
                large = a;
            }
            if (large.IData < current.IData)
            {
                do
                {
                    current = current.LeftChild;
                } while (current != null && large.IData < current.IData);
                if (current == null) return null;
                if (current.IData < small.IData) return LCA(current, small, large);
                // if we get here, current has the same IData as one of the two, the two are
                // in different subtrees, or not both are in the tree
                if (contains(current, small) && contains(current, large)) return current;
                // at least one isn't in the tree, return null
                return null;
            }
            else if (current.IData < small.IData)
            {
                do
                {
                    current = current.RightChild;
                } while (current != null && current.IData < small.IData);
                if (current == null) return null;
                if (current.IData < small.IData) return LCA(current, small, large);
                // if we get here, current has the same IData as one of the two, the two are
                // in different subtrees, or not both are in the tree
                if (contains(current, small) && contains(current, large)) return current;
                // at least one isn't in the tree, return null
                return null;
            }
            else // Not both in the same subtree
            {
                if (contains(current, small) && contains(current, large)) return current;
            }
            return null; // at least one not in tree
        }

        public static bool contains(Node root, Node target)
        {
            if (root == null) return false;
            if (root.IData == target.IData) return true;
            if (root.IData < target.IData) return contains(root.RightChild, target);
            return contains(root.LeftChild, target);
        }
    }
}
0
public static Node LCA(Node root, Node a, Node b)
{

    if (root == null)
        return null;

    if (root.IData > a.IData && root.IData > b.IData)
        return LCA(root.LeftChild, a, b);
    if (root.IData < a.IData && root.IData < b.IData)
        return LCA(root.RightChild, a, b);

    return root;
}
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接