深圳网站建设公司信息,大连零基础网站建设培训哪里有,淘宝官网首页手机版,三星官方网站二叉搜索树的最近公共祖先 题目描述递归 剪枝代码演示#xff1a; 上期经典 题目描述 难度 - 中等 LC235 二叉搜索树的最近公共祖先 给定一个二叉搜索树, 找到该树中两个指定节点的最近公共祖先。 百度百科中最近公共祖先的定义为#xff1a;“对于有根树 T 的两个结点 p、q… 二叉搜索树的最近公共祖先 题目描述递归 剪枝代码演示 上期经典 题目描述 难度 - 中等 LC235 二叉搜索树的最近公共祖先 给定一个二叉搜索树, 找到该树中两个指定节点的最近公共祖先。 百度百科中最近公共祖先的定义为“对于有根树 T 的两个结点 p、q最近公共祖先表示为一个结点 x满足 x 是 p、q 的祖先且 x 的深度尽可能大一个节点也可以是它自己的祖先。” 例如给定如下二叉搜索树: root [6,2,8,0,4,7,9,null,null,3,5] 示例 1: 输入: root [6,2,8,0,4,7,9,null,null,3,5], p 2, q 8 输出: 6 解释: 节点 2 和节点 8 的最近公共祖先是 6。 示例 2: 输入: root [6,2,8,0,4,7,9,null,null,3,5], p 2, q 4 输出: 2 解释: 节点 2 和节点 4 的最近公共祖先是 2, 因为根据定义最近公共祖先节点可以为节点本身。 说明: 所有节点的值都是唯一的。 p、q 为不同节点且均存在于给定的二叉搜索树中。 递归 剪枝 搜索二叉树Binary Search Tree是一种树形结构它有一个特殊的特性对于每个节点其左子树中所有节点的值都小于该节点的值其右子树中所有节点的值都大于该节点的值。这种特性使得搜索效率非常高。 搜索二叉树具有以下特点 1.每个节点最多只有两个子节点分别称为左子节点和右子节点。 2.左子节点小于父节点右子节点大于父节点。 3.没有重复的节点。 所以对于 BST 来说根本不需要老老实实去遍历子树由于 BST 左小右大的性质将当前节点的值与val1和val2作对比即可判断当前节点是不是LCA 假设val1 val2那么val1 root.val val2则说明当前节点就是LCA若root.val比val1还小则需要去值更大的右子树寻找LCA若root.val比val2还大则需要去值更小的左子树寻找最近公共祖先。 题目中说了两个节点肯定在这颗树上因此可以省去不在的情况的判断。 代码演示
/*** Definition for a binary tree node.* public class TreeNode {* int val;* TreeNode left;* TreeNode right;* TreeNode(int x) { val x; }* }*/class Solution {TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {// 保证 val1 较小val2 较大int val1 Math.min(p.val, q.val);int val2 Math.max(p.val, q.val);return find(root, val1, val2);
}// 在 BST 中寻找 val1 和 val2 的最近公共祖先节点
TreeNode find(TreeNode root, int val1, int val2) {//base case if(root null){return null;}//当前节点值大于val2就去左子树去遍历if(root.val val2){return find(root.left,val1,val2);}// //当前节点值小于val1就去右子树去遍历if(root.val val1){return find(root.right,val1,val2);}//如果 val1 root.val val2 说明当前节点就是最近公共祖先return root;
}
}上期经典
leetcode236. 二叉树的最近公共祖先
