72【leetcode】经典算法- Lowest Common Ancestor of a Binary Search Tree（lct of bst）

本文主要是介绍72【leetcode】经典算法- Lowest Common Ancestor of a Binary Search Tree（lct of bst），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目描述：

一个二叉搜索树，给定两个节点a，b，求最小的公共祖先

        _______6______/              \___2__          ___8__/      \        /      \0      _4       7       9/  \3   5

例如：

2,8 ---->6 2,4----->2

原文描述：

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

According to the definition of LCA on Wikipedia: “The lowest common ancestor is defined between two nodes v and w as the lowest node in T that has both v and w as descendants (where we allow a node to be a descendant of itself).”

       _______6______/              \___2__          ___8__/      \        /      \0      _4       7       9/  \3   5

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

思路分析：

二叉树考虑递归的思路
如果a < = root <= b，可以确定root是lct
采用二分搜索的方式递归，root > a,b，继续遍历左子树，反之右边的子树
-在递归的开始判断空值的情况，直接返回root

代码：

/*** Definition for a binary tree node.* public class TreeNode {*     int val;*     TreeNode left;*     TreeNode right;*     TreeNode(int x) { val = x; }* }*/
public class Solution {public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {if(root == null || p == null || q == null)return root;if(p.val > root.val && q.val > root.val)return lowestCommonAncestor(root.right, p, q);else if(p.val < root.val && q.val < root.val)return lowestCommonAncestor(root.left, p, q);elsereturn root;}
}