树的遍历问题

给出一组数据，和一个递归定义的二叉树建树规则，将给定的数据按照递归定义的规则建成一棵二叉树。

LC 654 最大二叉树

var constructMaximumBinaryTree = function(nums) {
    const n = nums.length
    const dfs = (nums, l, r) => {
        if(l > r){
            return null
        }
        let max = -1
        let idx = -1
        for(let i = l; i <= r; i++){
            if(nums[i] > max){
                max = nums[i]
                idx = i
            }   
        }
        const node = new TreeNode(max)
        const left = dfs(nums, l, idx - 1)
        const right = dfs(nums, idx + 1, r)
        node.left = left
        node.right = right
        return node
    }
    return dfs(nums, 0, n - 1)
};

LC 998. 最大二叉树 II

var insertIntoMaxTree = function (root, val) {
    const dummy = new TreeNode(Infinity, null, root)
    const node = new TreeNode(val)
    const dfs = (root) => {
        if (!root) return node
        if (root.val < val) {
            node.left = root
            return node
        }
        if (root.val > val) {
            root.right = dfs(root.right)
            return root
        }
        return root
    }
    dfs(dummy)
    return dummy.right
};

LC 105 从前序与中序遍历序列构造二叉树

var buildTree = function(preorder, inorder) {
    const n = preorder.length
    const map = new Map()
    // 先一遍hash，保存inorder的节点位置，方便后续dfs定位左右子树范围
    for(let i = 0; i < n; i++){
        map.set(inorder[i], i)
    }

    function dfs(pl, pr, il, ir){
        if(pl > pr){
            return null
        }
        // 从preorder定位root(第一个元素)，从inorder划分左右子树范围
        const rootVal = preorder[pl]
        const rootNode = new TreeNode(rootVal)
        const idx = map.get(rootVal) // 定位inorder里root idx
        const leftLen = idx - il // 左子树节点数
        rootNode.left = dfs(pl + 1, pl + leftLen, il, idx - 1)
        rootNode.right = dfs(pl + leftLen + 1, pr, idx + 1, ir)
        return rootNode
    }
    return dfs(0, n - 1, 0, n - 1)
};

LC 106 从中序与后序遍历序列构造二叉树

var buildTree = function(inorder, postorder) {
    let n = inorder.length
    // 思路和105一样
    let map = new Map()
    for(let i = 0; i < n; i++){
        map.set(inorder[i], i)
    }

    function dfs(il, ir, pl, pr){
        if(pl > pr) return null
        let rootVal = postorder[pr]
        let idx = map.get(rootVal)
        let leftLen = idx - il

        let rootNode = new TreeNode(rootVal)
        rootNode.left = dfs(il, idx - 1, pl, pl + leftLen - 1)
        rootNode.right = dfs(idx + 1, ir, pl + leftLen, pr - 1)
        return rootNode
    }

    return dfs(0, n - 1, 0, n - 1)
};

结构判断问题

当给定一棵树的时候，对这棵树的结构进行判断是一类常见的问题。

这类问题一般是给定一棵树，判断这棵树的结构是否与另一棵树相同，是否是另一棵树的子树，或者是判断这棵树中是否有一部分满足某个条件。

由于这类问题涉及到一棵树与另一个结构的对比，所以特点就是两个指针在两棵树上同步遍历。每遍历一个节点，额外的指针也相应地进行移动，然后对这一组节点进行判断。如果一直到遍历完也没有判断失败，则结构判断成功，否则结构判断失败。

LC 100. 相同的树

var isSameTree = function(p, q) {
    function dfs(p, q){
        if(!p && !q) return true
        if((p && !q) || (!p && q)) return false
        let left = dfs(p.left, q.left)
        let right = dfs(p.right, q.right)
        return left && right && p.val === q.val
    }
    return dfs(p, q)
};

LC 572. 另一个树的子树
复用LC 100的方法，递归比较

var isSubtree = function (root, subRoot) {
    function dfs(p, q) {
        if(!p) return false
        return isSameTree(p, q) || dfs(p.left, q) || dfs(p.right, q)
    }
    return dfs(root, subRoot)
};

LC 1367 二叉树中的链表

var isSubPath = function(head, root) {
    function dfs(head, root){
        if(!head) return true
        if(!root) return false
        if(head.val !== root.val) return false
        return dfs(head.next, root.left) || dfs(head.next, root.right)
    }
    if(!root) return false
    return dfs(head, root) || isSubPath(head, root.left) || isSubPath(head, root.right)
};

数据压缩问题

有一类最简单的压缩编码方式就是直接把文件内容用 数据 * 重复次数 的形式表示，称为游程编码（run-length encoding，RLE）。

RLE 的缺点：只对特定序列有效，例如图像文件和可执行文件。文本文件无效，因为文本中的连续字符不常见。

LC 443. 压缩字符串

var compress = function(chars) {
    const n = chars.length
    let k = 0 // rewrite idx
    let j = 0 // start
    let i = 0 // end
    while(i < n){
        while(i < n && chars[i] === chars[j]){
            i++
        }
        chars[k++] = chars[j]
        let length = i - j
        if(length > 1){
            let len = String(length)
            let idx = 0
            while(idx < len.length){
                chars[k++] = len[idx++]
            }
        }
        j = i
    }
    return k
};

LC 1313 解压缩编码列表

var decompressRLElist = function(nums) {
    const n = nums.length
    let i = 0 // freq
    let j = 1 // val
    const res = []
    while(j < n){
        let freq = nums[i]
        const val = nums[j]
        while(freq--){
            res.push(val)
        }
        i = j + 1
        j += 2
    }
    return res
};

LC 900 RLE 迭代器

var RLEIterator = function(encoding) {
    this.encoding = encoding
    this.freqIdx = 0
};

RLEIterator.prototype.next = function(n) {
    while(n && this.freqIdx < this.encoding.length){
        let len = Math.min(n, this.encoding[this.freqIdx])
        this.encoding[this.freqIdx] -= len
        n -= len
        if(n > 0 && this.encoding[this.freqIdx] === 0){
            this.freqIdx += 2
        }
    }
    return this.freqIdx < this.encoding.length ? this.encoding[this.freqIdx + 1] : -1
};

序列化反序列化

有一个程序，如果希望在执行这个程序的过程中可以保存程序中的对象，即望将对象存储在磁盘上，便于以后检索，这就是持久化。

持久化的手段是序列化。它是一个将任意复杂的对象转成对象的文本或二进制表示的过程。同时必须能够将对象经过序列化后的形式恢复到原有的对象。序列化有一些常见的协议，比如：JSON、XML、Thrift、Protobuf…

在 Python 中，这种序列化过程是 pickle，可以将对象转换成字符串、磁盘上的文件或者任何类似于文件的对象，也可以将这些字符串、文件或任何类似于文件的对象转换成原来的对象。

LC 297. 二叉树的序列化与反序列化

var serialize = function(root) {
    let path = ''
    const dfs = (root) => {
        if(!root){
            path += '#,'
            return
        }
        path += root.val + ','
        dfs(root.left)
        dfs(root.right)
    }
    dfs(root)
    return path
};

var deserialize = function(path) {
    let idx = 0 // 注意idx需要作为全局变量
    const dfs = (path) => {
        if(path[idx] === '#'){
            idx += 2 // 跳过'#,'
            return null
        }
        let start = idx
        while(path[idx] !== ',') idx++ // 有可能是多位数，所以需要走到逗号才代表一个完整的val
        const node = new TreeNode(+path.substring(start, idx))
        idx += 1 // 再次跳过数字后面的逗号
        node.left = dfs(path, idx)
        node.right = dfs(path, idx)
        return node
    }
    return dfs(path)
};

LC 606 根据二叉树创建字符串

var tree2str = function(root) {
    let path = ''
    const dfs = (root) => {
        if(!root) return
        path += root.val
        if(root.left){
            path += '('
            dfs(root.left)
            path += ')'
        }
        if(!root.left && root.right){
            path += '()'
        }
        if(root.right){
            path += '('
            dfs(root.right)
            path += ')'
        }
    }
    dfs(root)
    return path
};

LC 449. 序列化和反序列化二叉搜索树

var serialize = function(root) {
    const arr = []
    const dfs = (root) => {
        if(!root){
            return
        }
        arr.push(root.val)
        dfs(root.left)
        dfs(root.right)
    }
    dfs(root)
    const res = arr.join(',')
    return res
};

var deserialize = function(data) {
    const arr = data.length ? data.split(',') : []
    let idx = 0
    // 不能保证node val都不重复，所以不好用hash表去存储每个节点，且不让用全局变量
    // 利用BST的特性，left < root < right，dfs方法里传节点的合法区间，如果当前节点不符合区间要求，则退出
    const dfs = (min, max) => {
        if(idx >= arr.length || arr[idx] < min || arr[idx] > max) return null
        const curVal = +arr[idx] // 要转型
        const node = new TreeNode(curVal)
        idx += 1
        node.left = dfs(min, curVal)
        node.right = dfs(curVal + 1, max)
        return node
    }
    return dfs(-Infinity, Infinity)
};

LC 331. 验证二叉树的前序序列化

var isValidSerialization = function(preorder) {
    let idx = 0
    preorder += ',' // 补充一个逗号，方便判断
    const dfs = () => {
        if(idx === preorder.length){
            // 如果递归到字符串最后一个位置了，但是还需要往下则说明不合法
            return false
        }
        if(preorder[idx] === '#'){
            // 递归到空节点
            idx += 2
            return true
        }
        while(preorder[idx] !== ',') idx += 1
        idx += 1
        return dfs() && dfs()
    }
    // 如果递归还没结束但数组已经遍历完，或 递归结束但数组还没遍历完，则说明给定的序列不是一个合法的前序遍历
    if(!dfs()) return false
    return idx === preorder.length
};

自底向上整合子树结果

「后序遍历」
有很多对树上的信息进行统计的应用问题，可以抽象为树的后序遍历。在后序遍历过程中，需要将子树的答案交给当前节点，根据需求进行整合后，再继续向根节点传。整棵树遍历完成后，根节点整合后的就是统计结果。

LC 124. 二叉树中的最大路径和

var maxPathSum = function(root) {
    let res = -Infinity
    const dfs = (root) => {
        if(!root) return 0
        const left = dfs(root.left)
        const right = dfs(root.right)
        res = Math.max(res, left + right + root.val, right + root.val, left + root.val, root.val)
        return Math.max(Math.max(left, right) + root.val, root.val)
    }
    dfs(root)
    return res
};
// 更优化点的版本
var maxPathSum = function(root) {
    let res = -Infinity
    const dfs = (root) => {
        if(!root) return 0
        const left = Math.max(0, dfs(root.left)) // 和0做个max，减少负数的考虑
        const right = Math.max(0, dfs(root.right))
        res = Math.max(res, left + right + root.val)
        return Math.max(Math.max(left, right) + root.val, root.val)
    }
    dfs(root)
    return res
};

LC 979. 在二叉树中分配硬币

var distributeCoins = function(root) {
    let res = 0
    const dfs = (root) => {
        if(!root) return 0
        const left = dfs(root.left)
        const right = dfs(root.right)
        const total = root.val + left + right - 1
        if(total > 0 || total < 0){
            res += Math.abs(total)
        }
        return total
    }
    dfs(root)
    return res
};

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

var findFrequentTreeSum = function(root) {
    const count = {}
    let max = -Infinity
    const dfs = (root) => {
        if(!root) return 0
        const left = dfs(root.left)
        const right = dfs(root.right)
        const sum = left + right + root.val
        if(!count[sum]) count[sum] = 0
        count[sum] += 1
        max = Math.max(max, count[sum])
        return sum
    }

    dfs(root)
    const res = []
    for(let prop in count){
        if(count[prop] === max){
            res.push(prop)
        }
    }
    return res
};

LC 563. 二叉树的坡度

var findTilt = function(root) {
    let sum = 0
    const dfs = (root) => {
        if(!root) return 0
        const left = dfs(root.left)
        const right = dfs(root.right)
        sum += Math.abs(left - right)
        return left + right + root.val
    }
    dfs(root)
    return sum
};

LC 1325. 删除给定值的叶子节点

var removeLeafNodes = function(root, target) {
    const dfs = (root, target) => {
        if(!root) return null
        root.left = dfs(root.left, target)
        root.right = dfs(root.right, target)
        if(!root.left && !root.right && root.val === target){
            return null
        }
        return root
    }
    return dfs(root, target)
};

LC 652. 寻找重复的子树

var findDuplicateSubtrees = function(root) {
    const map = new Map() // key是序列，value是node
    const res = new Set() // 保存重复的子树
    // 这个做法复杂度是O(n^2)，因为要对每个节点都进行路径的序列化，最差是单链的情况，则所有子树的序列长度之和要N^2
    const dfs = (root) => {
        if(!root) return ''
        let path = ''
        path += String(root.val) + ','
        path += dfs(root.left) + ','
        path += dfs(root.right) + ','

        if(map.has(path)){
            res.add(map.get(path))
        }else{
            map.set(path, root)
        }
        return path
    }
    dfs(root)
    return [...res]
};

var findDuplicateSubtrees = function(root) {
    const map = new Map() // key是三元组的hash，value是[node, idx]
    const res = new Set() // 保存重复的子树
    let idx = 0
    // 这里对之前的序列化进行优化，可以用一个三元组直接表示一棵子树 [root, left, right]
    // 而idx对应一个三元组，如果路径相同，则他们的idx也相同
    const dfs = (root) => {
        if(!root) return ''
        const path = [root.val, dfs(root.left), dfs(root.right)]
        const hash = path.toString()
        if(map.has(hash)){
            const [node, existedId] = map.get(hash)
            res.add(node)
            return existedId
        }else{
            idx++
            map.set(hash, [root, idx])
            return idx
        }
    }
    dfs(root)
    return [...res]
};

LC 1372. 二叉树中的最长交错路径

var longestZigZag = function (root) {
    let res = 0
    const dfs = (root, dir, len) => {
        if(!root) return
        res = Math.max(res, len)
        // 自顶向下的
        if(dir === 'left'){
            dfs(root.left, 'right', len + 1)
            dfs(root.right, 'left', 1) // 如果没路可走了，则重置路线，由于他是从parent节点来的，所以len是1
        }else{
            dfs(root.right, 'left', len + 1)
            dfs(root.left, 'right', 1)
        }
    }
    dfs(root, 'left', 0) // 因为root节点没有parent，所以从root出发时的len的0
    dfs(root, 'right', 0)
    return res
};

LC 1373 二叉搜索子树的最大键值和

var maxSumBST = function(root) {
    let max = 0
    const dfs = (root) => {
        // 这个地方最小值返回Inf，最大值返回-Inf，可以保证在回溯到上一层时判断 root < leftMax 和 root > rightMin 恒不成立，再由parent返回
        if(!root) return [Infinity, -Infinity, 0] 
        const [leftMin, leftMax, leftSum] = dfs(root.left)
        const [rightMin, rightMax, rightSum] = dfs(root.right)
        // 判断是不是BST的时候用的是左边的max和右边的min进行比较
        if(root.val <= leftMax || root.val >= rightMin) return [-Infinity, Infinity, 0]
        const sum = leftSum + rightSum + root.val
        max = Math.max(max, sum)
        // 而返回的时候是 左边与root的Min 和 右边与root的Max
        return [Math.min(leftMin, root.val), Math.max(rightMax, root.val), sum]
    }
    dfs(root)
    return max
};

LC 426 将二叉搜索树转化为排序的双向链表

var treeToDoublyList = function(root) {
    let prev = null
    let head = null

    const dfs = (root) => {
        if(!root) return
        dfs(root.left)

        if(!prev){
            head = root // 走到左子树最左端，设head
        }else{
            prev.right = root
            root.left = prev
        }
        prev = root // 更新prev

        dfs(root.right)
    }

    if(!root) return // 这里还需要额外判空，不然后面赋值head.left会报错
    dfs(root)

    head.left = prev
    prev.right = head
    return head
};