本文共 1066 字，大约阅读时间需要 3 分钟。

给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。

百度百科中最近公共祖先的定义为：“对于有根树 T 的两个结点 p、q，最近公共祖先表示为一个结点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”

例如，给定如下二叉树: root = [3,5,1,6,2,0,8,null,null,7,4]

题解：先对这棵树遍历，遍历找到每个数的父节点。之后对第一个结点进行访问，并将其父节点存储。对第二个结点访问，如果其出现在存储中，返回，否则继续找其父亲。

package com.lcz.leetcode;/** * 二叉树的最近公共祖先 */import java.util.*;public class Leetcode236 {
   	class TreeNode{
   		int val;		TreeNode left;		TreeNode right;		TreeNode(int x){
   			val = x;		}	}	// 哈希表存储父节点	HashMap
   
     parent = new HashMap<>();	// 存储是否访问过	HashSet
    
      visited = new HashSet<>();	public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
           // 对其遍历		dfs(root);				while(p!=null) {
   			visited.add(p.val);			p = parent.get(p.val);		}						while(q!=null) {
   			if(visited.contains(q.val)) {
   				return q;			}			q = parent.get(q.val);		}				return null;    }	private void dfs(TreeNode root) {
   		if(root.left!=null) {
   			parent.put(root.val,root);			dfs(root.left);		}				if(root.right!=null) {
   			parent.put(root.val,root);			dfs(root.right);		}			}}
    
   

转载地址：http://xwwdf.baihongyu.com/