【前端面试】二叉树递归模板和题解

递归模板和步骤

- - 递归题目的通用步骤
  - 递归模板总结
  - - 1. 树的遍历（DFS）
    - 2. 二叉树的最大深度
    - 3. 二叉树的最近公共祖先
  - 递归题目的记忆技巧

递归题目的通用步骤

明确递归函数的功能：确定递归函数的输入参数和返回值，明确函数的功能。
基准情况（递归终止条件）：设立一个或多个递归终止条件，确保递归能够结束。
递归步骤：将问题分解为更小的子问题，通过递归调用自身解决这些子问题。
合并结果：将子问题的解合并成原问题的解。

递归模板总结

1. 树的遍历（DFS）

前序遍历（根 -> 左 -> 右）

function preorderTraversal(root) {
    let result = [];
    function traverse(node) {
        if (node !== null) {
            result.push(node.val);  // 访问根节点
            traverse(node.left);    // 递归遍历左子树
            traverse(node.right);   // 递归遍历右子树
        }
    }
    traverse(root);
    return result;
}

中序遍历（左 -> 根 -> 右）

function inorderTraversal(root) {
    let result = [];
    function traverse(node) {
        if (node !== null) {
            traverse(node.left);    // 递归遍历左子树
            result.push(node.val);  // 访问根节点
            traverse(node.right);   // 递归遍历右子树
        }
    }
    traverse(root);
    return result;
}

后序遍历（左 -> 右 -> 根）

function postorderTraversal(root) {
    let result = [];
    function traverse(node) {
        if (node !== null) {
            traverse(node.left);    // 递归遍历左子树
            traverse(node.right);   // 递归遍历右子树
            result.push(node.val);  // 访问根节点
        }
    }
    traverse(root);
    return result;
}

2. 二叉树的最大深度

function maxDepth(root) {
    if (root === null) {
        return 0;
    }
    let leftDepth = maxDepth(root.left);
    let rightDepth = maxDepth(root.right);
    return Math.max(leftDepth, rightDepth) + 1;
}

3. 二叉树的最近公共祖先

function lowestCommonAncestor(root, p, q) {
    if (root === null || root === p || root === q) {
        return root;
    }
    let left = lowestCommonAncestor(root.left, p, q);
    let right = lowestCommonAncestor(root.right, p, q);
    if (left !== null && right !== null) {
        return root;
    }
    return left !== null ? left : right;
}