【leetcode-236】二叉樹的最近公共祖先
題目
給定一個二叉樹, 找到該樹中兩個指定節點的最近公共祖先，
百度百科中最近公共祖先的定義為：“對于有根樹 T 的兩個節點 p、q，最近公共祖先表示為一個節點 x，滿足 x 是 p、q 的祖先且 x 的深度盡可能大（一個節點也可以是它自己的祖先），
解法
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
if (root == null || root.val == p.val || root.val == q.val) return root;
TreeNode right = lowestCommonAncestor(root.right, p, q);
TreeNode left = lowestCommonAncestor(root.left, p, q);
if (left == null) return right;
if (right == null) return left;
return root;
}
}
提交
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/352130.html
標籤：其他