A Backtracking Solution


  • 0
    L
    public TreeNode LowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        List<TreeNode> listP = new List<TreeNode>(), listQ = new List<TreeNode>();
        findPath(listP, root, p);
        findPath(listQ, root, q);
        for (int i = 0; i < listP.Count; i++)
            if (i == listQ.Count || listP[i] != listQ[i])
                return listP[i - 1];
        return listP[listP.Count - 1];
    }
    
    private void findPath(List<TreeNode> list, TreeNode root, TreeNode target){
        if (root == target) list.Add(root);
        else if (root != null){
            list.Add(root);
            findPath(list, root.left, target);
            if (list[list.Count - 1] == target) return;
            findPath(list, root.right, target);
            if (list[list.Count - 1] == target) return;
            list.RemoveAt(list.Count - 1);
        }
    }

Log in to reply
 

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