LeetCode 236. 二叉树的最近公共祖先 Java 实现思路递归后序遍历从根节点开始递归· 如果当前节点为空或当前节点就是 p 或 q直接返回当前节点。· 分别递归左右子树得到 left 和 right。· 如果 left 和 right 都非空说明 p 和 q 分别在左右两侧当前节点就是最近公共祖先。· 否则返回非空的那一个说明两个目标节点都在同一侧或只找到了其中一个。Java 代码classSolution{publicTreeNodelowestCommonAncestor(TreeNoderoot,TreeNodep,TreeNodeq){// 递归终止条件if(rootnull||rootp||rootq){returnroot;}// 后序遍历先处理左右子树TreeNodeleftlowestCommonAncestor(root.left,p,q);TreeNoderightlowestCommonAncestor(root.right,p,q);// 左右都找到了说明 p、q 分布在两侧当前节点就是 LCAif(left!nullright!null){returnroot;}// 否则返回非空的那一侧returnleft!null?left:right;}}复杂度分析· 时间复杂度O(n)每个节点最多访问一次。· 空间复杂度O(h)递归栈深度为树高。最坏情况下链状树为 O(n)。示例// 树结构// 3// / \// 5 1// / \ / \// 6 2 0 8// / \// 7 4p5,q1→3p5,q4→5p6,q4→5关键点· 递归函数含义在以 root 为根的子树中寻找 p 和 q 的最近公共祖先。· 如果当前节点就是 p 或 q直接返回它因为不可能再往下找到更近的祖先。· 左右子树返回值都非空说明两个目标节点分居两侧当前节点即为答案。· 只需要一次 DFS无需额外存储路径。附迭代写法父指针 祖先集合classSolution{publicTreeNodelowestCommonAncestor(TreeNoderoot,TreeNodep,TreeNodeq){MapTreeNode,TreeNodeparentnewHashMap();DequeTreeNodestacknewArrayDeque();parent.put(root,null);stack.push(root);// 遍历整棵树记录每个节点的父节点while(!parent.containsKey(p)||!parent.containsKey(q)){TreeNodenodestack.pop();if(node.left!null){parent.put(node.left,node);stack.push(node.left);}if(node.right!null){parent.put(node.right,node);stack.push(node.right);}}// 记录 p 到根的所有祖先SetTreeNodeancestorsnewHashSet();while(p!null){ancestors.add(p);pparent.get(p);}// 从 q 向上找第一个在 p 祖先集合中的节点while(!ancestors.contains(q)){qparent.get(q);}returnq;}}迭代写法时间复杂度 O(n)空间复杂度 O(n)适合不想用递归或树很深的情况。
