二叉树

前序遍历

根 -> 左 -> 右

function preorderTraversal(root: TreeNode | null): number[] {
    function dfs(root) {
        if (!root) return // 节点不存在，跳出
 
        res.push(root.val) // 根
        dfs(root.left) // 左
        dfs(root.right) // 右
    }
 
    let res = []
    dfs(root)
    return res
};

中序遍历

左 -> 根 -> 右

function inorderTraversal(root: TreeNode | null): number[] {
    function dfs(root) {
        if (!root) return // 节点不存在，跳出
 
        dfs(root.left) // 左
        res.push(root.val) // 根
        dfs(root.right) // 右
    }
 
    let res = []
    dfs(root)
    return res
};

后序遍历

左 -> 右 -> 根

function postorderTraversal(root: TreeNode | null): number[] {
    function dfs(root) {
        if (!root) return // 节点不存在，跳出
 
        dfs(root.left) // 左
        dfs(root.right) // 右
        res.push(root.val) // 根
    }
 
    let res = []
    dfs(root)
    return res
};

层序遍历

上 -> 中 -> 下

function levelOrder(root: TreeNode | null): number[][] {
    function bfs(root) {
        if (!root) return // 节点不存在，跳出
 
        let level = [root]
        while (level.length > 0) {
            let nextLevel = []
            for (let l of level) {
                if (l.left) nextLevel.push(l.left)
                if (l.right) nextLevel.push(l.right)
            }
            res.push(level.map(l => l.val))  
            level = nextLevel // 更新下一层
        }
    }
 
    let res = []
    bfs(root)
    return res
};

节点个数

使用前序遍历，记录节点个数

function countNodes(root: TreeNode | null): number {
    function dfs(root) {
        if (!root) return // 节点不存在，跳出
 
        count++ // 根
        dfs(root.left) // 左
        dfs(root.right) // 右
    }
 
    let count = 0
    dfs(root)
    return count
};

最大深度

最大深度 = 子节点的最大深度 + 1

function maxDepth(root: TreeNode | null): number {
    if (!root) return 0
 
    let [left, right] = [maxDepth(root.left), maxDepth(root.right)]
    return Math.max(left, right) + 1
};

最小深度

最小深度 = 子节点的最小深度 + 1（需要左右节点都存在）

function minDepth(root: TreeNode | null): number {
    if (!root) return 0
    if (!root.left && !root.right) return 1
    if (!root.left) return minDepth(root.right) + 1
    if (!root.right) return minDepth(root.left) + 1
    return Math.min(minDepth(root.left), minDepth(root.right)) + 1
};

平衡二叉树

遍历树的最大深度
每轮递归，检查 l - r

function isBalanced(root: TreeNode | null): boolean {
    function dfs(root) {
        if (!root) return 0
 
        let [l, r] = [dfs(root.left), dfs(root.right)]
        if (Math.abs(l - r) > 1) res = false
        return Math.max(l, r) + 1
    }
 
    let res = true
    dfs(root)
    return res
};

二叉树的直径

遍历树的最大深度
每轮递归，比较 l + r

function diameterOfBinaryTree(root: TreeNode | null): number {
    function dfs(root) {
        if (!root) return 0
 
        let [l, r] = [dfs(root.left), dfs(root.right)]
        res = Math.max(res, l + r)
        return Math.max(l, r) + 1
    }
 
    let res = 0
    dfs(root)
    return res
};

相同的树

树 a, b 相同，需要满足 a.left === b.left 和 a.right === b.right

function isSameTree(p: TreeNode | null, q: TreeNode | null): boolean {
    if (!p && !q) return true
    if (!p || !q) return false
    if (p.val !== q.val) return false
    return isSameTree(p.left, q.left) && isSameTree(p.right, q.right)
};

对称二叉树

树 a, b 对称，需要满足 a.left === b.right 和 a.right === b.left

function isSymmetric(root: TreeNode | null): boolean {
    function dfs(p, q) {
        if (!p && !q) return true
        if (!p || !q) return false
        if (p.val !== q.val) return false
        return dfs(p.left, q.right) && dfs(p.right, q.left)
    }
 
    return dfs(root, root)
};

翻转二叉树

function invertTree(root) {
    if (!root) return root;
 
    [root.left, root.right] = [invertTree(root.right), invertTree(root.left)]
    return root
};

合并二叉树

function mergeTrees(root1: TreeNode | null, root2: TreeNode | null): TreeNode | null {
    if (!root1) return root2
    if (!root2) return root1
    
    let merged = new TreeNode(
        root1.val += root2.val,
        mergeTrees(root1.left, root2.left),
        mergeTrees(root1.right, root2.right)
    )
    return merged
};

路径总和

前序遍历，同时计算路径和

function hasPathSum(root: TreeNode | null, targetSum: number): boolean {
    function dfs(root, sum) {
        if (!root) return
 
        sum += root.val // 根
        if (!root.left && !root.right) { // 叶子节点
            if (sum === targetSum) res = true
        }
        dfs(root.left, sum) // 左
        dfs(root.right, sum) // 右
    }
 
    let res = false
    dfs(root, 0)
    return res
};

数字之和

前序遍历，同时计算路径和

function sumNumbers(root: TreeNode | null): number {
    function dfs(root, sum) {
        if (!root) return
 
        sum = 10 * sum + root.val //根
        if (!root.left && !root.right) res += sum
        dfs(root.left, sum) // 左
        dfs(root.right, sum) // 右
    }
 
    let res = 0
    dfs(root, 0)
    return res
};