My java solution using backtracking technique


  • 0
    S
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        List<TreeNode> pPath = new ArrayList<TreeNode>();
        List<TreeNode> qPath = new ArrayList<TreeNode>();
        backTrack(root, p, q, new ArrayList<TreeNode>(), pPath, qPath);
        for (int i = 0; i < Math.min(pPath.size(), qPath.size()); i++) {
            if (pPath.get(i) != qPath.get(i)) {
                return pPath.get(i-1);
            }
        }
        return pPath.size() > qPath.size() ? qPath.get(qPath.size()-1) : pPath.get(pPath.size()-1);
    }
    
    private void backTrack(TreeNode root, TreeNode p, TreeNode q, List<TreeNode> path,
                           List<TreeNode> pPath, List<TreeNode> qPath) {
        if (root == null) return;
        path.add(root);
        if (path.get(path.size()-1) == p) pPath.addAll(path);
        if (path.get(path.size()-1) == q) qPath.addAll(path);
        backTrack(root.left, p, q, path, pPath, qPath);
        backTrack(root.right, p, q, path, pPath, qPath);
        path.remove(root);
    }
    

    I found the most voted version not quite intuitive, so I tried using backtracking to solve this problem.


Log in to reply
 

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