package question;

import java.util.LinkedList;
import java.util.List;

/*
 @author: Roderland
 @create: 2020年09月27日---10:09
*/
public class Question235 {
 public static void main(String[] args) {
 TreeNode t1 = new TreeNode(6);
 TreeNode t2 = new TreeNode(2);
 TreeNode t3 = new TreeNode(4);
 //TreeNode t4 = new TreeNode(4);
 t1.left=t2;
 t2.right=t3;
 // t3.left=t4;
 new Question235().lowestCommonAncestor(t1, t2, t3);
 }
 List<TreeNode> list1 = new LinkedList<>();
 List<TreeNode> list2 = new LinkedList<>();
 public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
 if (p==q) return p;
 dfs(root, p);
 dfs2(root, q);
 int len = Math.min(list1.size(), list2.size());
 list1.forEach(System.out::print);
 System.out.println();
 list2.forEach(System.out::print);
 for (int i = 0; i < len; i++) {
 if (list1.get(i)!=list2.get(i)) return list1.get(i-1);
 }
 return list1.get(len-1);
 }

 public boolean dfs(TreeNode root, TreeNode p) {
 if (root==null) return false;
 list1.add(root);
 if (root==p) {
 return true;
 }
 if (dfs(root.left, p)) {
 return true;
 }
 if (dfs(root.right, p)) {
 return true;
 }
 list1.remove(list1.size()-1);
 return false;
 }
 public boolean dfs2(TreeNode root, TreeNode p) {
 if (root==null) return false;
 list2.add(root);
 if (root==p) {
 return true;
 }
 if (dfs2(root.left, p)) {
 return true;
 }
 if (dfs2(root.right, p)) {
 return true;
 }
 list2.remove(list2.size()-1);
 return false;
 }
}