LeetCode

[py-tofee]

二叉树的深度(https://leetcode-cn.com/problems/er-cha-shu-de-shen-du-lcof/)

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */

思路一：二叉树深度 = 左子树深度 + 右子树深度 + 子树根节点（1）

/**
 * @param {TreeNode} root
 * @return {number}
 */
var maxDepth = function(root) {
    const depth = (node) => {
        if (node === null) {
            return 0
        }
        return Math.max(depth(node.left), depth(node.right)) + 1
    }
    return depth(root)
};

思路二：二叉树深度 = 树的层数

/**
 * @param {TreeNode} root
 * @return {number}
 */
var maxDepth = function(root) {
    let len = 0
    let queue = []
    root && queue.push(root)
    while(queue.length > 0) {
        len++
        let list = []
        queue.forEach((node) => {
            node.left && list.push(node.left)
            node.right && list.push(node.right)
        })
        queue = list
    }
    return len
};

[py-tofee]

判断是否是平衡二叉树

思路：每个节点的左右子树深度相差不能大于1

/**
 * @param {TreeNode} root
 * @return {boolean}
 */
var isBalanced = function(root) {
    const depth = (node) => {
        if (node === null) return 0 // 叶子节点
        let leftLen = depth(node.left)
        if (leftLen == -1) return -1 // 左子树不是平衡二叉树
        let rightLen = depth(node.right)
        if (rightLen == -1) return -1 // 右子树不是平衡二叉树
        return Math.abs(leftLen - rightLen) < 2 ? Math.max(leftLen, rightLen) + 1 : -1
    }
    return depth(root) !== -1
};

[py-tofee]

二叉树的镜像

每个节点的左右子树交换

/**
 * @param {TreeNode} root
 * @return {TreeNode}
 */
var mirrorTree = function(root) {
    const traverse = (node) => {
        if (node === null ) return root
        let left = node.left // 暂存左子树
        node.left = node.right
        node.right = left
        traverse(node.left)
        traverse(node.right)
        return root
    }
    return traverse(root)
};