练习

LeetCode.104.二叉树的最大深度

/**
 * 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 maxDepth = function (root) {
    let res = 0;
    const dfs = (n, l) => {
        if (!n) return
        if (!n.left && !n.right) {
            res = Math.max(res, l)
        }
        dfs(n.left, l + 1)
        dfs(n.right, l + 1)
    }
    dfs(root, 1)
    return res
};

LeetCode.111. 二叉树的最小深度

/**
 * 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 minDepth = function (root) {
    if (!root) return 0;

    let q = [[root, 1]];
    while (q.length) {
        const [n, d] = q.shift();
        if (!n.right && !n.left) return d;

        if (n.right) q.push([n.right, d + 1])
        if (n.left) q.push([n.left, d + 1])
    }

};

LeetCode.102. 二叉树的层序遍历

/**
 * 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 levelOrder = function (root) {
    if (!root) return [];

    let q = [[root, 0]]
    let res = [];
    while (q.length) {
        const [node, num] = q.shift();
        if (Array.isArray(res[num])) {
            res[num].push(node.val)
        } else {
            res[num] = [node.val]
        }

        if (node.left) q.push([node.left, num + 1])
        if (node.right) q.push([node.right, num + 1])
    }
    return res;
};

LeetCode.94. 二叉树的中序遍历

递归版

/**
 * 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 inorderTraversal = function(root) {
    if(!root) return [];
    let res = [];
    let d = (node) => {
        if(!node) return
        d(node.left);
        res.push(node.val);
        d(node.right)

    }
    d(root)
    return res
};

非递归版

/**
 * 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 inorderTraversal = function (root) {
    if (!root) return [];
    let stack = [];
    let q = root;
    let res = [];
    while (stack.length || q){
        while(q){
            stack.push(q);
            q = q.left
        }
        let node = stack.pop();
        res.push(node.val)
        q = node.right;
    }

    return res;
};

LeetCode.112. 路径总和

/**
 * 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) return false

    let d = (node, sums) => {
        if (node.left && d(node.left, sums + node.left.val)) return true
        if (node.right && d(node.right, sums + node.right.val)) return true
        if (!node.left && !node.right && sums === targetSum) return true
    }

    return !!d(root,root.val)
};