JZ68二叉搜索樹的最近公共祖先
描述
給定一個二叉搜索樹, 找到該樹中兩個指定節點的最近公共祖先，
1.對于該題的最近的公共祖先定義:對于有根樹T的兩個節點p、q，最近公共祖先LCA(T,p,q)表示一個節點x，滿足x是p和q的祖先且x的深度盡可能大，在這里，一個節點也可以是它自己的祖先.
2.二叉搜索樹是若它的左子樹不空，則左子樹上所有節點的值均小于它的根節點的值； 若它的右子樹不空，則右子樹上所有節點的值均大于它的根節點的值
3.所有節點的值都是唯一的，
4.p、q 為不同節點且均存在于給定的二叉搜索樹中，
資料范圍:
3<=節點總數<=10000
0<=節點值<=10000
思路：非遞回，利用二叉搜索樹的特點，左子樹<根節點<右子樹
若p,q都比當前結點的值小，說明最近公共祖先結點在當前結點的左子樹上，繼續檢查左子樹；
若p,q都比當前結點的值大，說明最近公共祖先結點在當前結點的右子樹上，繼續檢查右子樹；
若p,q中一個比當前結點的值大，另一個比當前結點的值小，則當前結點為最近公共祖先結點
代碼
package esay.JZ68二叉搜索樹的最近公共祖先;
import java.util.*;
class TreeNode {
int val = 0;
TreeNode left = null;
TreeNode right = null;
public TreeNode(int val) {
this.val = val;
}
}
public class Solution {
/**
* 代碼中的類名、方法名、引數名已經指定，請勿修改，直接回傳方法規定的值即可
*
* @param root TreeNode類
* @param p int整型
* @param q int整型
* @return int整型
*/
public int lowestCommonAncestor(TreeNode root, int p, int q) {
// write code here
//方法1、非遞回
/*TreeNode curNode = root;
while(true) {
if (p < curNode.val && q < curNode.val) {
curNode = curNode.left;
} else if (p > curNode.val && q > curNode.val) {
curNode = curNode.right;
} else {
return curNode.val;
}
}*/
//方法2、遞回
if (root == null) {
return -1;
}
if (p < root.val && q < root.val) {
return lowestCommonAncestor(root.left, p, q);
} else if (p > root.val && q > root.val) {
return lowestCommonAncestor(root.right, p, q);
} else {
return root.val;
}
}
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/535132.html
標籤：Java
上一篇：Java反應式編程（3）