活跃农民
- 积分
- 346
- 大米
- 颗
- 鳄梨
- 个
- 水井
- 尺
- 蓝莓
- 颗
- 萝卜
- 根
- 小米
- 粒
- 学分
- 个
- 注册时间
- 2018-1-26
- 最后登录
- 1970-1-1
|
BST和BT解法的共同点:都根据 if(root ==p || root == q || (rootVal < q.val && rootVal > p.val)) 判断最小公共节点
不同点:BST,根据root值和p,q的比较,决定是继续往左还是往右搜索,直接返回
BT,要搜索左右两棵子树,然后根据返回的值,觉得返回哪个节点。
附上我的具体代码,仅供参考
BST:
- public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
- if(root == null){
- return null;
- }
-
- if(p.val > q.val){
- return lowestCommonAncestor(root, q, p);
- }
-
- int rootVal = root.val;
- if(root ==p || root == q || (rootVal < q.val && rootVal > p.val)){
- return root;
- }else if(rootVal > q.val){
- return lowestCommonAncestor(root.left, p, q);
- }else{
- return lowestCommonAncestor(root.right, p, q);
- }
-
-
- }
复制代码
BT:
- public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
- if(root != null){
- System.out.println(root.val);
- }
- 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 && right != null){
- System.out.println("Ok" + root.val);
- return root;
- }
-
- return left == null? right:left;
- }
复制代码
|
|