网站网页设计内容,html网站源代码,搭建网站实时访问地图,不干净的网站做性目录
236. 二叉树的最近公共祖先
代码#xff1a;
运行结果#xff1a; 给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。 百度百科中最近公共祖先的定义为#xff1a;“对于有根树 T 的两个节点 p、q#xff0c;最近公共祖先表示为一个节点 x#xff0c;满足…
目录
236. 二叉树的最近公共祖先
代码
运行结果 给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。 百度百科中最近公共祖先的定义为“对于有根树 T 的两个节点 p、q最近公共祖先表示为一个节点 x满足 x 是 p、q 的祖先且 x 的深度尽可能大一个节点也可以是它自己的祖先。” 示例 1 输入root [3,5,1,6,2,0,8,null,null,7,4], p 5, q 1
输出3
解释节点 5 和节点 1 的最近公共祖先是节点 3 。示例 2 输入root [3,5,1,6,2,0,8,null,null,7,4], p 5, q 4
输出5
解释节点 5 和节点 4 的最近公共祖先是节点 5 。因为根据定义最近公共祖先节点可以为节点本身。示例 3 输入root [1,2], p 1, q 2
输出1提示 树中节点数目在范围 [2, 105] 内。-109 Node.val 109所有 Node.val 互不相同 。p ! qp 和 q 均存在于给定的二叉树中。 代码 /*** 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) {// proot 则 q 在 root 的左或右子树中// qroot 则 p 在 root 的左或右子树中// 即题目提示一个节点也可以是它自己的祖先if(rootnull||rootp||rootq) return root;// 不是则让左右节点继续往下递归在本层递归看来这步是给left赋值看看有没有p,q在左子树上TreeNode leftlowestCommonAncestor(root.left,p,q);// 与上一步一样TreeNode rightlowestCommonAncestor(root.right,p,q);// 如果left 和 right都不为空说明此时root就是最近公共节点// 如果left为空right不为空就返回right说明目标节点是通过right返回的反之亦然if(left ! null right ! null) return root;if(leftnull) return right;return left;}
} 运行结果
