leetcode tree习题第二集

2020-01-27 by 杜宏伟

树习题的第二集

可能做任何事情都是这样的吧。遇到一件难事,无解,然后学习别人的思想,然后就会了。下次遇到也会了。不过在参考别人的思想之前一定得自己先冥思苦想,这样效果会好。还有一种情况是创新,这种就只有一个办法,全身心投入,不计代价。创新是很难的,所以创新更需要站在巨人的肩膀上创新,需要已经了解所有前人的思想,需要已经到达了前人所到达的高度。

二叉搜索树迭代器

迭代的办法和用栈遍历的思想差不多,把根左入栈,这样出的时候就是左根,这时再把右子树入栈,整体看就是左根右,正好是中序遍历


/**
 * @param {TreeNode} root
 */
var BSTIterator = function (root) {
  this.stack = []
  this.push(root)
};
BSTIterator.prototype.push = function (root) {
  if (!root) return
  this.stack.push(root)
  let cur = root.left

  while (cur) {
    this.stack.push(cur)
    cur = cur.left
  }
}
/**
 * @return the next smallest number
 * @return {number}
 */
BSTIterator.prototype.next = function () {
  if (this.hasNext()) {
    let node = this.stack.pop()
    this.push(node.right)
    return node.val
  }
  else return null
};

/**
 * @return whether we have a next smallest number
 * @return {boolean}
 */
BSTIterator.prototype.hasNext = function () {
  return !!this.stack.length
};

二叉树的右视图

给定一棵二叉树,想象自己站在它的右侧,按照从顶部到底部的顺序,返回从右侧所能看到的节点值

最简单的方式是递归右子树,再递归左子树,把第一个深度增加的节点放入结果

/**
 * @param {TreeNode} root
 * @return {number[]}
 */
var rightSideView = function (root) {
  let result = []
  let curLevel = -1
  function helper(root, level) {
    if (!root) return
    if (level > curLevel) {
      result.push(root.val)
      curLevel = level
    }
    helper(root.right, level + 1)
    helper(root.left, level + 1)
  }
  helper(root, 0)
  return result
};

完全二叉树的节点个数

给出一个完全二叉树,求出该树的节点个数。

二分法,用树完全二叉做二分,天然简单许多,因为肯定能一分为二。

一个完全满二叉树的结点个数是 2**h-1 个,h是树高,根结点的高度为 1

  1. 算出左右子树的最大左结点高度
  2. 相同,就抛掉左子树
  3. 不同,就抛掉子树,同时减掉 2**(h-1)/2 个结点
/**
 * @param {TreeNode} root
 * @return {number}
 */
function getLevel(root) {
 if(!root) return 0
  let level = 1
  let cur = root.left
  while (cur) {
    level++
    cur = cur.left
  }
  return level
}
var countNodes = function (root) {
  if(!root) return 0;
  let maxLevel = getLevel(root)
  let subCount = 0;
  function helper(root, maxLevel) {
    if (maxLevel === 1) return
    let leftLevel = getLevel(root.left)
    let rightLevel = getLevel(root.right)
    if (leftLevel == rightLevel) {
      helper(root.right, maxLevel - 1)
    }
    else {
      subCount += 2 ** (maxLevel - 1) / 2
      helper(root.left, maxLevel - 1)
    }
  }
  helper(root, maxLevel)
  return 2 ** maxLevel - 1 - subCount
};

翻转二叉树

翻转一棵二叉树。

很简单的左右子树对换

var invertTree = function(root) {
  if (!root) return root
  let tmp = root.left
  root.left = root.right
  root.right = tmp
  invertTree(root.left)
  invertTree(root.right)
  return root
};

二叉搜索树的最近公共祖先

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

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

因为是搜索树,所以看是不是都在左边,在左边就抛弃右树,否则抛弃左对,其它情况root就是解,注意这个其它情况包括等于根,p在左q在右,q在左p在右,都可以统一算做其它。

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

二叉树的序列化与反序列化

序列化是将一个数据结构或者对象转换为连续的比特位的操作,进而可以将转换后的数据存储在一个文件或者内存中,同时也可以通过网络传输到另一个计算机环境,采取相反方式重构得到原数据。

请设计一个算法来实现二叉树的序列化与反序列化。这里不限定你的序列 / 反序列化算法执行逻辑,你只需要保证一个二叉树可以被序列化为一个字符串并且将这个字符串反序列化为原始的树结构。

可以深度优先,或广度优先。leetcode用的是广度优先。可以随意发挥。

打家劫舍 III

在上次打劫完一条街道之后和一圈房屋后,小偷又发现了一个新的可行窃的地区。这个地区只有一个入口,我们称之为“根”。 除了“根”之外,每栋房子有且只有一个“父“房子与之相连。一番侦察之后,聪明的小偷意识到“这个地方的所有房屋的排列类似于一棵二叉树”。 如果两个直接相连的房子在同一天晚上被打劫,房屋将自动报警。

计算在不触动警报的情况下,小偷一晚能够盗取的最高金额。

打家劫舍有三道题,层层递进。第一道题可以用dp方程

dp[i]=Math.max(dp[i-1],dp[i-2]+v[i]

dp[i]表示第i间房子可以得到的最大金额。dp[i-1]是第i间房子不偷可以得到的最大,dp[i-2]+v[i]是第i间房子偷可以得到的最大,这两种情况取最大值就是第i间房子可以得到的最大金额。

这个递归方程需要用到前面两层的状态,在打家劫舍 III就很难用了。打家劫舍 III 需要用上个状态递推出下一个状态,这也是这类问题的通用方式

直接从上个状态递推到本状态,需要两维。

dp[i][0]第i个房子不偷dp[i][0],第i个房子偷dp[i][1]

dp[i][0] = dp[i-1][1]
dp[i][1] = Math.max(dp[i-1][0],dp[i-1][1])

本题中因为是树,所以基本原理不变,但需要考虑一下左右子树

  1. 根结点偷,那么子树只能不偷
  2. 根结点不偷,那么子树可以偷也可以不偷,取最大值

双一次体现动态规划的思想,穷举所有情况,在每一步做出选择并记忆。

//根结点不偷,左右子树随意,取最大值即可。
dp[i][0] = Math.max(Math.max(left[0],left[1]),Math.max(right[0],right[1]))
//根结点偷,左右子树只能不偷。
dp[i][1] = left[i-1][0]+right[i-1][0]

虽然看起来麻烦,但还是应该掌握通用的方式,毕竟是方能的。特例能解决的方式遇到变化就解决不了了。


/**
 * @param {TreeNode} root
 * @return {number}
 */
var rob = function (root) {
  function helper(root) {
    let dp = [0, 0]
    if (!root) return dp

    let left = helper(root.left)
    let right = helper(root.right)

    dp[1] = left[0] + right[0] + root.val
    dp[0] = Math.max(left[0], left[1]) + Math.max(right[0], right[1])

    return dp
  }
  return Math.max(...helper(root))
}

左叶子之和

计算所有左叶子之和。注意,只有一个根结点的情况不算是左叶子啊

非常简单,可以讨论的地方就是看如何判断是左叶子。

我这里是传一个值,因为只有父结点才知道哪个是左,哪个是右。

也可以直接判断

 if (root.left!=null && root.left.left == null && root.left.right == null){
    temp+= root.left.val;
 }
var sumOfLeftLeaves = function (root) {
  let sum = 0
  function helper(root, isLeft) {
    if (!root) return
    if (!root.left && !root.right && isLeft) {
      sum += root.val
      return
    }
    helper(root.left, true)
    helper(root.right, false)
  }
  helper(root, false)
  return sum
};

路径总和 III

给定一个二叉树,它的每个结点都存放着一个整数值。

找出路径和等于给定数值的路径总数。

路径不需要从根节点开始,也不需要在叶子节点结束,但是路径方向必须是向下的(只能从父节点到子节点)。

有很多解法,不过我觉得最清晰的就是双递归。

/**
 * @param {TreeNode} root
 * @param {number} sum
 * @return {number}
 */
var pathSum = function (root, sum) {
  let count = 0;
  function helper(root, s) {
    if (!root) return
    s += root.val
    if (s === sum) {
      count++
    }
    helper(root.left, s)
    helper(root.right, s)
  }
  function cal(root) { 
    if(!root) return
    helper(root, 0)
    cal(root.left)
    cal(root.right)
  }
  cal(root)
  return count
};

删除二叉搜索树中的节点

给定一个二叉搜索树的根节点 root 和一个值 key,删除二叉搜索树中的 key 对应的节点,并保证二叉搜索树的性质不变。返回二叉搜索树(有可能被更新)的根节点的引用。

一般来说,删除节点可分为两个步骤:

首先找到需要删除的节点;

  1. 如果找到了,删除它。
  2. 说明: 要求算法时间复杂度为 O(h),h 为树的高度。

个人还是比较喜欢这种 cut,join 的方式的

这题的关键是如何在递归的过程中删除节点,通过返回值的方式巧妙的解决了这个问题。第一次遇到在一个函数中只在分支条件返回的情况。

/**
 * @param {TreeNode} root
 * @param {number} key
 * @return {TreeNode}
 */
var deleteNode = function (root, key) {
  if (root) {
    if (root.val > key) {
      root.left = deleteNode(root.left,key)
    }
    else if (root.val < key) {
      root.right = deleteNode(root.right,key)
    }
    else {
      return del(root)  
    }
  }
  return root
}
function del(root) {
  if (!root.left) {
    return root.right
  }
  if (!root.right) {
    return root.left
  }
  let joint = root.right
  while (joint.left) {
    joint = joint.left
  }
  joint.left = root.left

  return root.right
}

出现次数最多的子树元素和

每个子树的所有元素(包括根结点)的相加的和的频率最高的是哪个(几个)数

还是很考验功底的。很容易想到解法,但不容易处理可能返回一个值,也可能返回多个值,而且涉及到key,val,需要用到 map 和 array

/**
 * @param {TreeNode} root
 * @return {number[]}
 */
var findFrequentTreeSum = function (root) {
  let map = new Map()
  let max = -Infinity

  function helper(root) {
    if (!root) return 0

    let sum = root.val + helper(root.left) + helper(root.right)

    if (map.has(sum)) {
      let v = map.get(sum)
      map.set(sum, v + 1)
    }
    else {
      map.set(sum, 1)
    }
    max = Math.max(max, map.get(sum))
    return sum
  }
  helper(root)

  return [...map].filter(item => item[1] === max).map(item => item[0])
};

找树左下角的值

深度优先即可

在每个树行中找最大值

您需要在二叉树的每一行中找到最大的值。

可以用深度优先,只保留每个level下的最大值即可

二叉搜索树的最小绝对差

给定一个所有节点为非负值的二叉搜索树,求树中任意两节点的差的绝对值的最小值。

利用二叉搜索树的特点,中序遍历即是一个升序排列,差的最小值只可能出现在相邻的两个节点。

把二叉搜索树转换为累加树

给定一个二叉搜索树(Binary Search Tree),把它转换成为累加树(Greater Tree),使得每个节点的值是原来的节点值加上所有大于它的节点值之和。

最容易想到的方法是两次遍历。第一次遍历先计算出和,第二次中序遍历,把和减去当前节点值加到这个节点上。

反中序遍历。就是右中左遍历,因为已遍历的节点的和就是所有大的结点的和,所以只需要一次遍历即可。

二叉树的直径

给定一棵二叉树,你需要计算它的直径长度。一棵二叉树的直径长度是任意两个结点路径长度中的最大值。这条路径可能穿过根结点。

左右子树的最大深度相加+1,就是最大节点数,最后再减1,获取直径。递归每个节点作为根结点的情况,速度打败99%

/**
 * @param {TreeNode} root
 * @return {number}
 */
var diameterOfBinaryTree = function (root) {
 if(!root) return 0
  let max = 0
  function helper(root) {
    if (!root) return 0
    let left = helper(root.left)
    let right = helper(root.right)
    max =Math.max(left + right + 1,max)
    return Math.max(left, right) + 1
  }
  let m=helper(root)

  max = Math.max(m, max)
  return max-1
};

二叉树的坡度

给定一个二叉树,计算整个树的坡度。

一个树的节点的坡度定义即为,该节点左子树的结点之和和右子树结点之和的差的绝对值。空结点的的坡度是0。

整个树的坡度就是其所有节点的坡度之和。

其实是求子树和的问题,和都知道了,坡度也就知道了。速度打败99%

/**
 * @param {TreeNode} root
 * @return {number}
 */
var findTilt = function (root) {

  let sum = 0;
  function helper(root) {
    if (!root) return 0
    let left = helper(root.left)
    let right = helper(root.right)
    sum += Math.abs(left - right)
    return left+right+root.val    
  }
  helper(root)
  return sum
};

另一个树的子树

给定两个非空二叉树 st,检验 s 中是否包含和 t 具有相同结构和节点值的子树。s 的一个子树包括 s 的一个节点和这个节点的所有子孙。s 也可以看做它自身的一棵子树。

递归,时间复杂度 O(mn)。开始写的时候我没有写辅助函数 check,虽然也可以,结果超时。因为有节点值相同的情况,当前 root.val === t.val 还需要判断 root.left,root.rightt是不是包含关系。

还有一种方法是先遍历得到一个字符串,然后判断s的字符串是不是包含t的字符串。需要注意节点的值之前要有分隔符。时间复杂度为 O(m^2+n^2+mn)

/**
 * @param {TreeNode} s
 * @param {TreeNode} t
 * @return {boolean}
 */
var isSubtree = function (s, t) {
  let result = false
  function check(s, t) {
    if (!s && !t) return true
    if (!s || !t) return false
    if (s.val !== t.val) return false
    return check(s.left, t.left) && check(s.right, t.right) 
  }
  function helper(root) {
    if (!root || result) {
      return
    }

    result = check(root, t)
    helper(root.left)
    helper(root.right)
  }
  helper(s, t)
  return result
};

根据二叉树创建字符串

你需要采用前序遍历的方式,将一个二叉树转换成一个由括号和整数组成的字符串。

空节点则用一对空括号 "()" 表示。而且你需要省略所有不影响字符串与原始二叉树之间的一对一映射关系的空括号对。

在返回的时候注意右子树为空不返回'()'即可

/**
 * @param {TreeNode} t
 * @return {string}
 */
var tree2str = function (root) {
  if (!root) return ''
  if (!root.left && !root.right) return `${root.val}`

  let left = tree2str(root.left)
  let right = tree2str(root.right)
  if (!right) {
    return `${root.val}(${left})`
  }
  else {
    return `${root.val}(${left})(${right})`
  }
};

合并二叉树

给定两个二叉树,想象当你将它们中的一个覆盖到另一个上时,两个二叉树的一些节点便会重叠。

你需要将他们合并为一个新的二叉树。合并的规则是如果两个节点重叠,那么将他们的值相加作为节点合并后的新值,否则不为 NULL 的节点将直接作为新二叉树的节点。

从下至上构造。遇到相同的,复用t1的节点即可,不要新new节点,这样速度和内存效率都明显提升。

/**
 * @param {TreeNode} t1
 * @param {TreeNode} t2
 * @return {TreeNode}
 */
var mergeTrees = function (t1, t2) {

  function helper(t1, t2) {
    if (!t1 && !t2) return null
    if (!t1) return t2
    if (!t2) return t1

    t1.val = t1.val + t2.val
    t1.left = helper(t1.left, t2.left)
    t1.right = helper(t1.right, t2.right)

    return t1
  }
  return helper(t1, t2)
};

在二叉树中增加一行

给定一个二叉树,根节点为第1层,深度为 1。在其第 d 层追加一行值为 v 的节点。

添加规则:给定一个深度值 d (正整数),针对深度为 d-1 层的每一非空节点 N,为 N 创建两个值为 v 的左子树和右子树。

将 N 原先的左子树,连接为新节点 v 的左子树;将 N 原先的右子树,连接为新节点 v 的右子树。

如果 d 的值为 1,深度 d - 1 不存在,则创建一个新的根节点 v,原先的整棵树将作为 v 的左子树。

如果小于1直接在上面加一个节点,否则,递归到目标level,做增加结点处理

/**
 * @param {TreeNode} root
 * @param {number} v
 * @param {number} d
 * @return {TreeNode}
 */
var addOneRow = function (root, v, d) {
  let maxLevel = 0
  function helper(root, level) {
    if (!root) return null
    maxLevel = Math.max(maxLevel, level)
    if (d === level + 1) {
      let node = new TreeNode(v)
      node.left = root.left
      root.left = node
      node = new TreeNode(v)
      node.right = root.right
      root.right = node
    }
    helper(root.left, level + 1)
    helper(root.right, level + 1)
  }
  if (d <= 1) {
    let node = new TreeNode(v)
    node.left = root
    return node
  }
  helper(root, 1)
  return root
};

寻找重复的子树

给定一棵二叉树,返回所有重复的子树。对于同一类的重复子树,你只需要返回其中任意一棵的根结点即可。

两棵树重复是指它们具有相同的结构以及相同的结点值。

这道题的判题有问题,[1,21,3,4,null,2,4,null,null,14],把 [21,4],[2,14]当成是相同子树了。晕

方法是标记法。let key = node.val.toString() + helper(node.left) + helper(node.right);

两数之和 IV - 输入 BST

给定一个二叉搜索树和一个目标结果,如果 BST 中存在两个元素且它们的和等于给定的目标结果,则返回 true。

这就是一水题。因为没用到搜索树的特性。就是遍历+hasMap就可以,和怎么遍历没什么关系。

如果硬要和搜索树扯上关系,可以先序遍历存起来,再前后双指针。但和直接遍历相比,没有优势。

最大二叉树

给定一个不含重复元素的整数数组。一个以此数组构建的最大二叉树定义如下:

二叉树的根是数组中的最大元素。 左子树是通过数组中最大值左边部分构造出的最大二叉树。 右子树是通过数组中最大值右边部分构造出的最大二叉树。 通过给定的数组构建最大二叉树,并且输出这个树的根节点。

递归解法,可以优化的部分,可以不用slice新数组,直接用原数组,用startIndex,endIndex记录位置即可。

/**
 * @param {number[]} nums
 * @return {TreeNode}
 */
var constructMaximumBinaryTree = function (nums) {
  if (nums.length === 0) return null
  let max = Math.max(...nums)
  let index = nums.indexOf(max)
  let node = new TreeNode(max)
  node.left = constructMaximumBinaryTree(nums.slice(0, index))
  node.right = constructMaximumBinaryTree(nums.slice(index + 1))
  return node
};

修剪二叉搜索树

给定一个二叉搜索树,同时给定最小边界L 和最大边界 R。通过修剪二叉搜索树,使得所有节点的值在[L, R]中 (R>=L) 。你可能需要改变树的根节点,所以结果应当返回修剪好的二叉搜索树的新的根节点。

根据二叉树的特点,小于跳过当前节点,递归处理右子树;大于就跳过当前节点,递归处理左子树。 符合要求的,保留当前节点,继续处理下面的子树

/**
 * @param {TreeNode} root
 * @param {number} L
 * @param {number} R
 * @return {TreeNode}
 */
var trimBST = function (root, L, R) {
  if (!root) return null

  if (root.val >= L && root.val <= R) {
    root.left = trimBST(root.left, L, R)
    root.right = trimBST(root.right, L, R)
    return root
  }
  else if (root.val < L) {
    return trimBST(root.right, L, R)
  }
  else {
    return trimBST(root.left, L, R)
  }

};

我叫杜宏伟,前端开发。

一直想写博客,在2018的年的最后几天,终于上线了。

对于前端开发,一个特点就是太零散,很容易会了后面忘了前面,所以归纳总结很重要。再有就是分享,做前端好多年,以前都是看你们写的文章, 现在我也开始写一些,希望可以帮到入行的小伙伴。微信号 duhongwei5775

欢迎转载,只需注明作者,出处即可

版权说明:署名 4.0 国际(CC BY 4.0)