1. 题目

在这里插入图片描述

2. 思路

(1) DFS

首先利用深度优先搜索和栈存储从根结点到p结点的路径，由于q结点必然位于这条路径上的某个结点的子树上，因此依次弹出栈中的结点，检查q结点是否在以该结点为根的二叉树上，找到最低的一个结点返回即可。
可以存储前一个被弹出的结点，检查到当前结点时，前一个被弹出的结点必然不满足要求，因此检查时可以直接排除前一个被弹出的结点。

3. 代码

import java.util.Deque;
import java.util.LinkedList;

public class Test {
    public static void main(String[] args) {
    }
}

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode(int x) {
        val = x;
    }
}

class Solution {
    private Deque<TreeNode> stack;
    private TreeNode p;
    private TreeNode q;
    private TreeNode pre;

    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        stack = new LinkedList<>();
        this.p = p;
        this.q = q;
        query(root);
        while (!stack.isEmpty()) {
            root = stack.peek();
            if (exist(root)) {
                break;
            }
            pre = stack.pop();
        }
        return root;
    }

    private void query(TreeNode root) {
        if (stack.peek() == p || root == null) {
            return;
        }
        stack.push(root);
        query(root.left);
        query(root.right);
        if (stack.peek() == p) {
            return;
        }
        stack.pop();
    }

    private boolean exist(TreeNode root) {
        if (root == null || root == pre) {
            return false;
        }
        if (root == q) {
            return true;
        }
        return exist(root.left) || exist(root.right);
    }
}