package week02;

/**

* @创建人 luoxiang

* @创建时间 2019/6/14 14:49

* @描述 LeetCode : 236. 二叉树的最近公共祖先 https://leetcode-cn.com/problems/lowest-common-ancestor-of-a-binary-tree/

*/

public class LowestCommonAncestorBinaryTree236 {

public static void main(String[] args) {

TreeNode node = new TreeNode(3);

node.left = new TreeNode(5);

node.right = new TreeNode(1);

node.left.left = new TreeNode(6);

node.left.right = new TreeNode(2);

node.left.right.left = new TreeNode(7);

node.left.right.right = new TreeNode(4);

node.right.left = new TreeNode(0);

node.right.right = new TreeNode(8);

System.out.println(new LowestCommonAncestorBinaryTree236().lowestCommonAncestor(node, node.right, node.left).toString());

}

/**

* Method 1 : 递归 ，从左右子树中分别查找

* 时间复杂度 ： O(N)

* 空间复杂度 ： O(N)

*/

public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {

if (root == null || root == p || root == q) return root;

TreeNode left = lowestCommonAncestor(root.left, p, q);

TreeNode right = lowestCommonAncestor(root.right, p, q);

if (left != null && right != null) return root;

return left != null ? left : right;

}

}