路径 被定义为一条从树中任意节点出发,沿父节点-子节点连接,达到任意节点的序列。同一个节点在一条路径序列中 至多出现一次 。该路径 至少包含一个 节点,且不一定经过根节点。 路径和 是路径中各节点值的总和。 给你一个二叉树的根节点 root ,返回其 最大路径和 。
答案
var maxPathSum = function(root) {
let maxSum = Number.MIN_SAFE_INTEGER
const d = n => {
if (n === null) return 0
const leftSum = Math.max(0, d(n.left))
const rightSum = Math.max(0, d(n.right))
maxSum = Math.max(maxSum, n.val + leftSum + rightSum)
return n.val + Math.max(leftSum, rightSum)
}
d(root)
return maxSum
};
哈希表存左右节点的返回值
var maxPathSum = function(root) {
const stack = [], h = new WeakMap
let p = root, prev = null, maxSum = Number.MIN_SAFE_INTEGER
while (stack.length || p) {
while (p) {
stack.push(p)
p = p.left
}
const n = stack.pop()
if (n.right === null || n.right === prev) {
const leftSum = Math.max(0, h.get(n.left) || 0)
const rightSum = Math.max(0, h.get(n.right) || 0)
maxSum = Math.max(maxSum, n.val + leftSum + rightSum)
h.set(n, n.val + Math.max(leftSum, rightSum))
prev = n
} else {
stack.push(n)
p = n.right
}
}
return maxSum
};
给定一个二叉树,我们在树的节点上安装摄像头。 节点上的每个摄影头都可以监视其父对象、自身及其直接子对象。 计算监控树的所有节点所需的最小摄像头数量。
答案
字节跳动原题,动态规划三种状态,如上图所示:
a
b
c
状态转换关系:当前节点 n
左节点 l
右节点 r
n
a = l
c + r
c + 1n
b = min(n
a, l
a + r
b, r
a + l
b)n
c = min(n
a, l
b + r
b)var minCameraCover = function(root) {
const d = n => {
if (n === null) return [Number.MAX_SAFE_INTEGER, 0, 0]
const left = d(n.left)
const right = d(n.right)
const a = left[2] + right[2] + 1
const b = Math.min(a, Math.min(left[0] + right[1], right[0] + left[1]))
const c = Math.min(a, left[1] + right[1])
return [a, b, c]
}
return d(root)[1]
};
哈希表存左右节点的返回值
var minCameraCover = function(root) {
const stack = [], h = new WeakMap
let prev = null, p = root
while (stack.length || p) {
while (p) {
stack.push(p)
p = p.left
}
const n = stack.pop()
if (n.right === null || n.right === prev) {
const left = h.get(n.left) || [Number.MAX_SAFE_INTEGER, 0, 0]
const right = h.get(n.right) || [Number.MAX_SAFE_INTEGER, 0, 0]
const a = left[2] + right[2] + 1
const b = Math.min(a, Math.min(left[0] + right[1], right[0] + left[1]))
const c = Math.min(a, left[1] + right[1])
h.set(n, [a, b, c])
prev = n
} else {
stack.push(n)
p = n.right
}
}
return h.get(root)[1]
};