DFS C# solution


  • 0
    J
    public class Solution {
    public TreeNode LowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if(root==null || p==null ||q==null) { return root; }
        Dictionary<TreeNode, TreeNode> parent = new Dictionary<TreeNode, TreeNode>(); parent[root]=null;
        DFS(root, parent);
        List<TreeNode> list1=new List<TreeNode>();
        List<TreeNode> list2=new List<TreeNode>();
        TreeNode node=p;
        while(node!=null) { list1.Add(node); node=parent[node]; }
        node=q;
        while(node!=null) { list2.Add(node); node=parent[node]; }
        int i=list1.Count-1; int j=list2.Count-1; node=null;
        while(i>=0&&j>=0)
        {
            if(list1[i]==list2[j]) { node=list1[i]; i--; j--; }
            else { break; }
        }
        
        return node;
    }
    
    private void DFS(TreeNode node, Dictionary<TreeNode, TreeNode> parent)
    {
        if(node.left!=null)
        {
            parent[node.left]=node;
            DFS(node.left, parent);
        }
        if(node.right!=null)
        {
            parent[node.right]=node;
            DFS(node.right, parent);
        }
    }

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.