前端刷题路-Day10|刷题打卡

我心飞翔 分类:javascript

掘金团队号上线,助你 Offer 临门! 点击 查看详情

二叉树的最近公共祖先(题号235、236)

题目

给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。

百度百科中最近公共祖先的定义为:“对于有根树 T 的两个节点 pq,最近公共祖先表示为一个节点 x,满足 x pq 的祖先且 x 的深度尽可能大(一个节点也可以是它自己的祖先)。”

示例 1:

img

输入:root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1
输出:3
解释:节点 5 和节点 1 的最近公共祖先是节点 3 。
 

示例 2:

img

输入: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 != q
  • pq 均存在于给定的二叉树中。

链接

  • 普通二叉树
    leetcode-cn.com/problems/lo…
  • 二叉搜索树
    leetcode-cn.com/problems/lo…

解释

这是LeetCode的235和236两题,由于内容差不多,就放在一起了。

首先说说普通二叉树的解法,这种方法就有点不好理解了,但代码看上去十分简洁易懂,首先,判断当前节点是不是null如果是,直接返回,这一点毋庸置疑。

之后判断root是否等于q或者p,如果等于两者其中之一,就返回root节点。之后递归调用该函数,传入左节点和右节点,拿到左边和右边的值,如果左边的值是null,那证明qp都在右边,如果右边的值是null,那么返回左边,如果两边都是null,那么直接返回root节点,因为显然root节点就是qp的最近公共祖先了。

如果还是看不懂的话,就自己画图想想,或者去LeetCode看看答案,里面有图解,应该会有所帮助。

解决完普通二叉树后,二叉搜索树就简单很多了,因为可以利用它左右节点的大小关系来进行更简单的判断,条件也更清楚,而且这里可以使用递归和遍历两种方法,可操作性也更多了。

自己的答案

更好的方法(普通二叉树-递归)

var lowestCommonAncestor = function(root, p, q) {
  if (root === null) return null
  if (root.val === q.val || root.val === p.val) return root
  var left = lowestCommonAncestor(root.left, p, q)
      right = lowestCommonAncestor(root.right, p, q)
  if (left === null) {
    return right
  } else {
    if (right === null) {
      return left
    } else {
      return root
    }
  }
};
 

这里为了更直观,在判断上采用了root === null的写法,其实!root也是可以的。

更好的方法(二叉搜索树-递归)

var lowestCommonAncestor = function(root, p, q) {
  if (!root) return root
  if (root.val > p.val && root.val > q.val) {
    return lowestCommonAncestor(root.left, p, q)
  }
  if (root.val < p.val && root.val < q.val) {
    return lowestCommonAncestor(root.right, p, q)
  }
  return root
};
 

此为递归解法,如果根节点的值同时小于pq的值,那么证明pq在根节点的右边,之后递归调用右节点的值;同理可得,如果同时大于pq,那么证明p在根节点的左侧,取左子树进行下一步递归,最后不能满足同时大于或者小于`p`和值,那么证明当前的root就是二者的最近公共祖先节点,返回即可。

更好的方法2(二叉搜索树-遍历)

var lowestCommonAncestor = function(root, p, q) {
  if (!root) return root
  while (root) {
    if (root.val > p.val && root.val > q.val) {
      root = root.left
    } else if (root.val < p.val && root.val < q.val) {
      root = root.right 
    } else {
      return root
    }
  }
};
 

此写法为遍历写法,整体逻辑和递归类似,可以理解为一种不同的写法,在此不多做赘述,看看即可。

Pow(x, n)(题号50)

题目

实现 pow(x, n) ,即计算 xn 次幂函数(即,xn次方)。

示例 1:

输入:x = 2.00000, n = 10
输出:1024.00000
 

示例 2:

输入:x = 2.10000, n = 3
输出:9.26100
 

示例 3:

输入:x = 2.00000, n = -2
输出:0.25000
解释:2-2 = 1/22 = 1/4 = 0.25
 

提示:

  • -100.0 < x < 100.0
  • -231 <= n <= 231-1
  • -104 <= xn <= 104

链接

leetcode-cn.com/problems/po…

解释

这块就有点涉及到数学知识了,乍一看是很简单的一题,一直n-1即可,但实时告诉我没这么简单,在提交时发现n可能会巨大,然后就内存不足了,直接GG。

那么这个时候就要考虑到时间复杂度了,n-1的时间复杂度时O(n),此时显然需要降低时间复杂度,数学渣渣的我自然时没办法想出来的,讲真,看了答案后才知道,如果不看答案我应该永远都不会想到这种方法。

主要的逻辑很简单,利用幂的特性,如果幂指数为n,那么可以利用n / 2来减少一次递归或者遍历,此时之需要将本来的指改为其平方即可,由x变为x * x,这就完事了,那么具体到代码中去可能还需要考虑n的奇偶性,如果时奇数,那么需要用x来乘上上一步的结果,然后将n改为n-1,继续进行下一步循环。

到了这里这题就很简单了,直接看答案即可。

自己的答案

var myPow = function(x, n) {
  if (n === 0) return 1
  var res = 1
      flag = n > 0
      n = Math.abs(n)
  while (n > 0) {
    if (n === 1) break
    if (n % 2 === 1) {
      res *= x
      n--
    }
    x = x * x
    n = n / 2
  }
  return flag ? res * x : 1 / (res * x)
};
 

有点小丑陋,主要是在判断n的正负上,其实使用递归调用一次就好了,这里有点小费劲。

更好的方法(遍历)

var myPow = function(x, n) {
  if (n === 0) return 1
  if (n < 0) return myPow(1 / x, -n)
  var res = 1
  while (n > 1) {
    if (n % 2 === 1) {
      res = res * x
      n--
    }
    x = x * x
    n = n / 2
  }
  return res * x
};
 

这里就用递归调用的方法解决的n的正负问题

更好的方法(递归)

var myPow = function(x, n) {
  if (n === 0) return 1
  if (n < 0) return myPow(1 / x, -n)
  return n % 2 === 1 ? x * myPow(x, n - 1) : myPow( x * x, n / 2 )
};
 

PS:想查看往期文章和题目可以点击下面的链接:

这里是按照日期分类的👇

前端刷题路-目录(日期分类)

经过有些朋友的提醒,感觉也应该按照题型分类
这里是按照题型分类的👇

前端刷题路-目录(题型分类)

有兴趣的也可以看看我的个人主页👇

Here is RZ

回复

我来回复
  • 暂无回复内容