題目:
Given a binary search tree (BST), find the lowest common ancestor (LCA) of two given nodes in the BST.

According to the definition of LCA on Wikipedia: “The lowest common ancestor is defined between two nodes v and w as the lowest node in T that has both v and w as descendants (where we allow a node to be a descendant of itself).”

For example, the lowest common ancestor (LCA) of nodes 2 and 8 is 6. Another example is LCA of nodes 2 and 4 is 2, since a node can be a descendant of itself according to the LCA definition.

翻譯:
給定一個搜索二叉樹，找到給定的2個節點的最小共同祖先（LCA）。
根據維基百科對LCA的定義，最小共同祖先是定義在樹T中的一個最小節點，這個最小節點滿足，樹上的另外2個節點v和w都是它的子孫（這里我們允許一個是它自己的子孫）。
例如上圖中的2和8的LCA是6，2和4的LCA是2。

分析：
這道題的思路是從根節點這個共同祖先的節點開始，根據搜索二叉樹的性質，也就是任一節點的左子樹的所有節點的值一定會比該節點的小，右子樹一定會比該節點大，一步步找到最小的共同祖先。
而如果遍歷到某一節點時，2棵子樹的值既沒有都比該節點小，也沒有都比該節點大，只有2種可能：第一種可能是2棵子樹的值，一個比該節點大，一個比該節點小；另外一種可能其中至少有一個子樹的值等于該節點。不管是哪種可能，這個時候最小共同祖先都為該節點。

代碼：

/*** Definition for a binary tree node.* public class TreeNode {* int val;* TreeNode left;* TreeNode right;* TreeNode(int x) { val = x; }* }*/ public class Solution {public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {TreeNode LCA=root;while(true){if(p.val<LCA.val&&q.val<LCA.val){LCA=LCA.left;}else if(p.val>LCA.val&&q.val>LCA.val){LCA=LCA.right;}else{break;}}return LCA;} }

總結

以上是生活随笔為你收集整理的Leet Code OJ 235. Lowest Common Ancestor of a Binary Search Tree [Difficulty: Easy]的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。