首页 > 代码库 > LeetCode_Lowest Common Ancestor of a Binary Search Tree (Binary Tree)

LeetCode_Lowest Common Ancestor of a Binary Search Tree (Binary Tree)

Lowest Common Ancestor of a Binary Search Tree

一、题目描写叙述

技术分享

二、思路及代码

二叉搜索树有个性质:左子树的值都比根节点小,右子树的值比根节点大。那么我们的思路就是递归比較。
假设输入的两个节点的值比当前节点小,说明是在当前根节点的左子树中;反之则在右子树中。

假设当前根节点比一个大。比一个小。那么第一个出现的这种节点就是近期的父亲节点了。

/**
 * 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.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;
        }
    }
}

Lowest Common Ancestor of a Binary Tree

一、题目描写叙述

技术分享

二、思路及代码

假设是普通的二叉树。没有了二叉搜索树的特性。就要遍历;于是我们用到DFS遍历树

/**
 * 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 || root == p || root == q) return root; //找到p或者q节点,或者到最底层的叶子节点时,返回;
        TreeNode left = lowestCommonAncestor(root.left, p, q);
        TreeNode right = lowestCommonAncestor(root.right, p, q);

        if(left != null && right != null) return root; //找到了父节点
        return left != null ?

left : right; //所以假设都未找到,返回null } }

<script type="text/javascript"> $(function () { $(‘pre.prettyprint code‘).each(function () { var lines = $(this).text().split(‘\n‘).length; var $numbering = $(‘
    ‘).addClass(‘pre-numbering‘).hide(); $(this).addClass(‘has-numbering‘).parent().append($numbering); for (i = 1; i <= lines; i++) { $numbering.append($(‘
  • ‘).text(i)); }; $numbering.fadeIn(1700); }); }); </script>

LeetCode_Lowest Common Ancestor of a Binary Search Tree (Binary Tree)