ツリーの最も近い共通の親ノード

Javaはツリーの最も近い共通の親ノードを探します

問題

構想

コード

に質問
2つのツリーと2つのノードを指定し、この2つのノードが最も近い共通の親ノードを見つけます.

によって与えられた2つのノードは、必ずツリーに存在する.

ノードの値はランダムで、重複する可能性があります.ノードにはleftとrightの2つのサブノードしか含まれておらず、親ノードへのparentはありません.

この問題はLeetCode 236を参照することができる.
構想
2つのノードの存在を考慮します.

あるノードが別のノードの子または孫である場合、rootノードがそのうちの1つのノードに等しいと判断すればよい.

の2つのノードは2つのノードに属し、このとき2つのノードはrootノードの子または孫のノードであり、同時にrootである.移動とrootrightにはそれぞれ1つのノードが見つかります.

上記2つに該当する場合はroot.移動とrootright再帰判断.

rootノードから2つのノードへのパスをそれぞれ見つけてチェーンテーブルに保存し、パスを比較して最近の共通の親ノードを得る方法もあります.
コード#コード#
1、再帰方法

/*class TreeNode {
 *	  public int val;
 *	  public TreeNode left;
 *	  public TreeNode right;
 *	  public TreeNode(int val) {this.val = val;}
 *}
 */
public TreeNode findAncestor(TreeNode root, TreeNode node1, TreeNode node2) {
	if (root == null) return null;
	if (root == node1 || root == node2) return root;
	TreeNode left  = findAncestor(root.left,  node1, node2);
	TreeNode right = findAncestor(root.right, node1, node2);
	if (left != null && right != null) return root;
	return right == null ? left : right;
}

2、直接法

public TreeNode findAncestor(TreeNode root, TreeNode node1, TreeNode node2) {
	List<TreeNode> path1 = new ArrayList<>();
	List<TreeNode> path2 = new ArrayList<>();
	path1.add(root);
	getPath(root, node1, path1);
	path2.add(root);
	getPath(root, node2, path2);
	
	TreeNode res = null;
	for (int i = 0; i < path1.size() && i < path2.size(); i++) {
		if (path1.get(i) == path2.get(i))
			res = path1.get(i);
		else
			break;
	}
	return res;
}

private boolean getPath(TreeNode root, TreeNode node, List<TreeNode> path) {
	if (root == node) return true;
	if (root.left != null) {
		path.add(root.left);
		if (getPath(root.left, node, path)) return true;
		else path.remove(path.size()-1);
	}
	if (root.right != null) {
		path.add(root.right);
		if (getPath(root.right, node, path)) return true;
		else path.remove(path.size()-1);
	}
	reture false;
}