代码随想录——二叉搜索树的最近公共祖先（Leetcode235）

本文主要是介绍代码随想录——二叉搜索树的最近公共祖先（Leetcode235），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目链接

普通递归法

/*** 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(root == null || p == root || q == root){return root;}TreeNode left = lowestCommonAncestor(root.left, p, q);TreeNode right = lowestCommonAncestor(root.right, p, q);if(left != null && right != null){return root;}if(left == null){return right;}return left;}
}

利用二叉搜索树特性递归

/*** 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(root.val > p.val && root.val > q.val){return lowestCommonAncestor(root.left, p, q);}else if(root.val < p.val && root.val < q.val){return lowestCommonAncestor(root.right, p, q);}else{return root;}}
}

二叉搜索树最近公共祖先比普通二叉树公共祖先问题简单，不用使用回溯，二叉树自带方向性，遇到目标区间的节点可以直接返回。

这篇关于代码随想录——二叉搜索树的最近公共祖先（Leetcode235）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---