[leetcode] 树形结构算法练习

[liangbus]

今天的打卡题，正好是一道树相关的算法题，正好这方面也忘记得差不多了，一并做了几道类似的题目练习一下

199. 二叉树的右视图

一看到树相关的算法题，首先想到的就是深度/广度优先搜索，先序/后序遍历这些方法。

这道题深度优先会更简单一些，来分析

新建一个辅助函数 dfs，通过 depth 记录当前到达树的深度，因为每次都是首先遍历右子节点，所以，每一次先到达该层次的节点，即为本层次最右侧节点

写法很简单，递归就完事了。（递归虽然方便，但是缺点也很明显，就是不能过深，在 Chrome 下，最深调用栈大概是30000+，超过这个值会直接报异常）

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number[]}
 */
var rightSideView = function(root) {
    var res = []
    dfs(root, 0, res)
    return res
};

function dfs(root, depth, res) {
    if(root) {
        if(res.length === depth) {
            // 因为每次是先遍历右节点，所以当到达该深度时，必定是最右侧的子节点
            res.push(root.val)
        }
        dfs(root.right, depth + 1, res)
        dfs(root.left, depth + 1, res)
    }
}

广度优先搜索，就解决了递归过深的问题

分析：
通过一个数组，去把一个个节点，从上往下，从左往右加入数组中，这里最关键的地方就是每一层最后一个节点，这里通过每次循环开始前保存数组的长度，以其作为下标值进行判断，当 len = 0 时（非真正的数组长度），即当前层次最右边的值，已经挪到了数组的最前端（因为每一轮循环都会移除最前面的元素）。

var rightSideView = function(root) {
    if(!root) return []
    const res = []
    const queue = [root]
    while(queue.length) {
        let len = queue.length // 记录初始长度
        while(len > 0) {
            let node = queue.shift()
            if(len === 1) res.push(node.val)
            if(node.left) queue.push(node.left)
            if(node.right) queue.push(node.right)
            len--
        }
    }
    return res
};

[liangbus]

112. 路径总和

这道题的难度是简单，相比上面的更容易一点，自己也成功写出来了，不过的题目开始没看清楚，以为只要是和为 sum 的路径就可以，其实是根节点到叶子节点的路径，所以最后得加上，没有叶子节点的判断条件

思路：
深度优先搜索，将 sum 值减去当前节点的 val 值，然后递归去查找，假如找到等于目标 sum 值的节点，且该节点为叶子节点，返回 true

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @param {number} sum
 * @return {boolean}
 */
var hasPathSum = function(root, sum) {
    if(!root) return false
    return dfs(root, sum)
};
function dfs(root, sum) {
    if(root.val === sum && !root.left && !root.right) return true
    let leftRes = false
    let rightRes = false
    if(root.left) {
        leftRes = dfs(root.left, sum - root.val)
    }
    if(root.right) {
        rightRes = dfs(root.right, sum - root.val)
    }
    return (leftRes || rightRes)
}

[liangbus]

226. 翻转二叉树

这是一道经典而又简单级别的二叉树相关题目

遇到树相关的题目，其实很容易想到是用递归的方式

递归

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @return {TreeNode}
 */
var invertTree = function(root) {
    if(!root) return root
    const right = invertTree(root.right)
    const left = invertTree(root.left)
    root.left = right
    root.right = left
    return root
};

迭代

迭代是通过一个队列去实现，具体见注释

var invertTree = function(root) {
    if(!root) return root
    const queue = [] // 新建一个队列
    // 将根节点加进队头中
    queue.push(root)
    // 开始遍历，这里要实时检测列队长度
    // queue 为空时，即所有的节点都交换过了
    while (queue.length) {
        // 将队头节点移出，作为本次交换的子树的根节点
        const curNode = queue.shift()
        const swap = curNode.left
        curNode.left = curNode.right
        curNode.right = swap
        // 判断左右子节点非空，则加入队列末尾，这里每次都先根，后左、右遍历，其实就是我们所熟悉的层次遍历方法
        if(curNode.left !== null) queue.push(curNode.left)
        if(curNode.right !== null) queue.push(curNode.right)
    }
    // 返回根节点即可
    return root
};