56、二叉搜索树的最近公共祖先 LeetCode简单

题目描述

文章图片

文章图片

首先这个的前提条件是二叉搜索树：
对于二叉搜索树就是
二叉查找树(Binary Search Tree)，(又:二叉搜索树，二叉排序树)它或者是一棵空树，或者是具有下列性质的二叉树: 若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值; 若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值; 它的左、右子树也分别为二叉排序树。
因此这道题就变得十分简单了，如果给定的两个节点一个小于等于根节点，一个大于等于根节点，那么根节点就是最近的公共祖先，
这里需要注意的是p和q给出时可能不是按照p.val

/** * 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(p == q){ return p; } //将p节点默认作为左边的节点，q节点放在p的右边 TreeNode tem =null; if(p.val > q.val){ tem = q; q = p; p = tem; } if(p.val <= root.val && q.val >= root.val ){ return root; } while (true) { if(p.val <= root.val && q.val >= root.val){ break; } else if(p.val < root.val && q.val < root.val){ root = root.left; }else if (p.val > root.val && q.val > root.val) { root = root.right; } } return root; } }

文章图片

【56、二叉搜索树的最近公共祖先】排名较高的代码：
使用递归
还是递归简单啊，不需要转换，不需要考虑那么多的细节

class Solution { public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) { if (p.val root.val && q.val > root.val) { return lowestCommonAncestor(root.right, p, q); } return root; } }