[Leetcode] 236. The nearest common ancestor of binary trees

Topic describes

Given a binary tree, find the nearest common ancestor of the two specified nodes in the tree. // The definition of the nearest common ancestor in Baidu Encyclopedia is: "For the two nodes P and Q with root tree T, the nearest common ancestor // is first expressed as a node X, satisfying that X is the ancestor of P and Q and x is as deep as possible (a node can also // be its own ancestor).Copy the code

Answer key

/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } *} */ / this is the last common ancestor of the binary tree See https://leetcode-cn.com/problems/lowest-common-ancestor-of-a-binary-tree/solution/236-er-cha-shu-de-zui-jin-gong-gong- Zu-xian-hou-xu // / well written and illustrated, if you don't understand it, please read it. // // execution time: 7 ms, beating 99.93% user // memory consumption in all Java commits: Class Solution {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) return right; else if (right == null) return left; return root; }}Copy the code