leetCode 235. Lowest Common Ancestor of a Binary Search Tree 二排序樹問題

235. Lowest Common Ancestor of a Binary Search Tree

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

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

思路：

mine思路：

1.将各個節點的從root到節點的路徑都記錄下來vector&lt;vector&lt;int&gt;&gt;，vector中最後一個元素為目前節點。

2.找到目标的兩個vector，比較之找到較短的"根"

others思路：

在二叉查找樹種，尋找兩個節點的最低公共祖先。

1、如果a、b都比根節點小，則在左子樹中遞歸查找公共節點。

2、如果a、b都比根節點大，則在右子樹中查找公共祖先節點。

3、如果a、b一個比根節點大，一個比根節點小，或者有一個等于根節點，則根節點即為最低公共祖先。

代碼如下：(代碼實作為others思路)

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

<code>/**</code>

<code> </code><code>* Definition for a binary tree node.</code>

<code> </code><code>* struct TreeNode {</code>

<code> </code><code>*     int val;</code>

<code> </code><code>*     TreeNode *left;</code>

<code> </code><code>*     TreeNode *right;</code>

<code> </code><code>*     TreeNode(int x) : val(x), left(NULL), right(NULL) {}</code>

<code> </code><code>* };</code>

<code> </code><code>*/</code>

<code> </code> 

<code>class</code> <code>Solution {</code>

<code>public</code><code>:</code>

<code>    </code><code>TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {</code>

<code>        </code><code>int</code> <code>pVal = p-&gt;val;</code>

<code>        </code><code>int</code> <code>qVal = q-&gt;val;</code>

<code>        </code><code>int</code> <code>rootVal = root-&gt;val;</code>

<code>        </code><code>if</code><code>(pVal &lt; rootVal &amp;&amp; qVal &lt; rootVal)</code>

<code>        </code><code>{</code>

<code>            </code><code>return</code> <code>lowestCommonAncestor(root-&gt;left,p,q);</code>

<code>        </code><code>}</code>

<code>        </code><code>else</code> <code>if</code><code>(pVal &gt; rootVal &amp;&amp; qVal &gt; rootVal)</code>

<code>            </code><code>return</code> <code>lowestCommonAncestor(root-&gt;right,p,q);</code>

<code>        </code><code>return</code> <code>root;</code>

<code>    </code><code>}</code>

<code>};</code>

2016-08-07 09:47:25

本文轉自313119992 51CTO部落格，原文連結:http://blog.51cto.com/qiaopeng688/1835217