百强企业2013新校招笔试题(二)
作者:网络转载 发布时间:[ 2013/10/28 10:07:54 ] 推荐标签:面试
/* 若p为root的子孙,则返回true */
boolean covers(TreeNode root, TreeNode p) {
if (root == null) return false;
if (root == p) return true;
return covers(root.left, p) || covers(root.right, p);
}
TreeNode commonAncestorHelper(TreeNode root, TreeNode p,
TreeNode q) {
if (root == null) return null;
if (root == p || root == q) return root;
boolean is_p_on_left = covers(root.left, p);
boolean is_q_on_left = covers(root.left, q);
/* 若p和q不在同一边,则返回root */
if (is_p_on_left != is_q_on_left) return root;
/* 否则是在同一边,遍访那一边 */
TreeNode child_side = is_p_on_left ? root.left : root.right;
return commonAncestorHelper(child_side, p, q);
}
TreeNode commonAncestor(TreeNode root, TreeNode p, TreeNode q) {
if (!covers(root, p) || !covers(root, q)) { // 错误检查
return null;
}
return commonAncestorHelper(root, p, q);
}
但上述代码存在一些问题,读者可以进一步思考,后续可能会在编程艺术系列里详细阐述,可保持关注。
相关推荐
更新发布
功能测试和接口测试的区别
2023/3/23 14:23:39如何写好测试用例文档
2023/3/22 16:17:39常用的选择回归测试的方式有哪些?
2022/6/14 16:14:27测试流程中需要重点把关几个过程?
2021/10/18 15:37:44性能测试的七种方法
2021/9/17 15:19:29全链路压测优化思路
2021/9/14 15:42:25性能测试流程浅谈
2021/5/28 17:25:47常见的APP性能测试指标
2021/5/8 17:01:11