今日學(xué)習(xí)

找樹左下角的值

題目鏈接/文章講解/視頻講解：https://programmercarl.com/0513.%E6%89%BE%E6%A0%91%E5%B7%A6%E4%B8%8B%E8%A7%92%E7%9A%84%E5%80%BC.html

第一想法

這道題明顯迭代法更簡單氏仗，模板題，直接秒

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number}
 */
var findBottomLeftValue = function (root) {
    let res
    let queue = []
    queue.push(root)

    while (queue.length) {
        let length = queue.length
        for (let i = 0; i < length; i++) {
            let node = queue.shift()
            if(i == 0){
                res = node.val
            }
            node.left && queue.push(node.left)
            node.right && queue.push(node.right)
        }
    }
    return res
};

112. 路徑總和

題目鏈接/文章講解/視頻講解：https://programmercarl.com/0112.%E8%B7%AF%E5%BE%84%E6%80%BB%E5%92%8C.html

第一想法

迭代法有點(diǎn)像配套設(shè)施夺鲜，要記錄當(dāng)前的數(shù)值和當(dāng)前的node

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @param {number} targetSum
 * @return {boolean}
 */
var hasPathSum = function (root, targetSum) {
    if(root === null) return false;
    let valArr = [0]
    let nodeArr = [root]

    while (nodeArr.length) {
        let curNode = nodeArr.shift()
        let curVal = valArr.shift()

        curVal += curNode.val
        if (!curNode.left && !curNode.right && curVal === targetSum) {
            return true
        }
        if (curNode.left) {
            nodeArr.push(curNode.left);
            valArr.push(curVal);
        }
        // 右節(jié)點(diǎn)皆尔，將當(dāng)前的數(shù)值也對應(yīng)記錄下來
        if (curNode.right) {
            nodeArr.push(curNode.right);
            valArr.push(curVal);
        }

    }
    return false;
};

106.從中序與后序遍歷序列構(gòu)造二叉樹

題目鏈接/文章講解/視頻講解：https://programmercarl.com/0106.%E4%BB%8E%E4%B8%AD%E5%BA%8F%E4%B8%8E%E5%90%8E%E5%BA%8F%E9%81%8D%E5%8E%86%E5%BA%8F%E5%88%97%E6%9E%84%E9%80%A0%E4%BA%8C%E5%8F%89%E6%A0%91.html

第一想法

遞歸法，其實(shí)就是用后序遍歷獲得中間節(jié)點(diǎn)的值來分割中序遍歷

var buildTree = function(inorder, postorder) {
    if (!inorder.length) return null;
    const rootVal = postorder.pop(); // 從后序遍歷的數(shù)組中獲取中間節(jié)點(diǎn)的值谣旁， 即數(shù)組最后一個(gè)值
    let rootIndex = inorder.indexOf(rootVal); // 獲取中間節(jié)點(diǎn)在中序遍歷中的下標(biāo)
    const root = new TreeNode(rootVal); // 創(chuàng)建中間節(jié)點(diǎn)
    root.left = buildTree(inorder.slice(0, rootIndex), postorder.slice(0, rootIndex)); // 創(chuàng)建左節(jié)點(diǎn)
    root.right = buildTree(inorder.slice(rootIndex + 1), postorder.slice(rootIndex)); // 創(chuàng)建右節(jié)點(diǎn)
    return root;
}