《剑指 Offer（第 2 版）》树部分JavaScript题解

用户8921923

发布于 2022-10-24 18:47:48

3640

发布于 2022-10-24 18:47:48

文章被收录于专栏：全栈私房菜

《剑指 Offer （第 2 版）》树部分 JavaScript 题解

《剑指 Offer（第 2 版）》通行全球的程序员经典面试秘籍。剖析典型的编程面试题，系统整理基础知识、代码质量、解题思路、优化效率和综合能力这 5 个面试要点。

最近，把「树」部分的题刷完了。本文来分享下这些题的解法

07. 重建二叉树

输入某二叉树的前序遍历和中序遍历的结果，请构建该二叉树并返回其根节点。

假设输入的前序遍历和中序遍历的结果中都不含重复的数字。

「示例 1:」

Input: preorder = [3,9,20,15,7], inorder = [9,3,15,20,7]
Output: [3,9,20,null,null,15,7]

「示例 2:」

Input: preorder = [-1], inorder = [-1]
Output: [-1]

「限制：」

0 <= 节点个数 <= 5000

题目地址：https://leetcode-cn.com/problems/zhong-jian-er-cha-shu-lcof/

「解题思路」

对于任意一颗树而言，前序遍历的形式总是

[ 根节点, [左子树的前序遍历结果], [右子树的前序遍历结果] ]即根节点总是前序遍历中的第一个节点。而中序遍历的形式总是

[ [左子树的中序遍历结果], 根节点, [右子树的中序遍历结果] ]只要我们在中序遍历中定位到根节点，那么我们就可以分别知道左子树和右子树中的节点数目。由于同一颗子树的前序遍历和中序遍历的长度显然是相同的，因此我们就可以对应到前序遍历的结果中，对上述形式中的所有左右括号进行定位。

这样以来，我们就知道了左子树的前序遍历和中序遍历结果，以及右子树的前序遍历和中序遍历结果，我们就可以递归地对构造出左子树和右子树，再将这两颗子树接到根节点的左右位置。

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {number[]} preorder
 * @param {number[]} inorder
 * @return {TreeNode}
 */
var buildTree = function(preorder, inorder) {
    if (preorder.length === 0) return null;
    if (preorder === 1) return new TreeNode(preorder[0]);
    function build(preorderStart, preorderEnd, inorderStart, inorderEnd) {
        const root = new TreeNode(preorder[preorderStart]);
        const rootIndex = inorder.indexOf(preorder[preorderStart]);
        root.left = rootIndex === inorderStart ? null : 
            build(preorderStart + 1, preorderStart + rootIndex - inorderStart, inorderStart, rootIndex - 1);
        root.right = rootIndex === inorderEnd ? null : 
            build(preorderStart + rootIndex - inorderStart + 1, preorderEnd, rootIndex + 1, inorderEnd);
        return root;
    }
    return build(0, preorder.length - 1, 0, inorder.length - 1);
};

26. 树的子结构

输入两棵二叉树A和B，判断B是不是A的子结构。(约定空树不是任意一个树的子结构)

B是A的子结构，即 A中有出现和B相同的结构和节点值。

例如: 给定的树 A:

给定的树 B：

   4 
  /
 1

返回 true，因为 B 与 A 的一个子树拥有相同的结构和节点值。

「示例 1：」

输入：A = [1,2,3], B = [3,1]
输出：false

「示例 2：」

输入：A = [3,4,5,1,2], B = [4,1]
输出：true

「限制：」

0 <= 节点个数 <= 10000

题目地址：https://leetcode-cn.com/problems/shu-de-zi-jie-gou-lcof/

「解题思路」

递归，主要分为是否是子树，和两树是否相同两个函数

对于两树是否相同：如果A或B有一个是空的，那肯定不相同；然后判断A和B是否相同、A的左子树和B是否相同、A的右子树和B是否相同。
对于是否是子树：先判断B，如果空了说明遍历完了，是子树，返回true；再判断A，如果在B没空的前提下A空了，说明不是子树；然后判断值；最后继续递归各自左子树、右子树。

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} A
 * @param {TreeNode} B
 * @return {boolean}
 */
var isSubStructure = function(A, B) {
    if (!A || !B) return false;
    return isSame(A, B) || isSubStructure(A.left, B) || isSubStructure(A.right, B);
};

function isSame(A, B) {
    // B空了，说明B树遍历完了，是子树
    if(!B)
        return true;
    // 不符合上面情况的前提下A空了，说明B树还没遍历完，不是子树
    if(!A)
        return false;
    // 值不同，不是子树
    if(A.val !== B.val)
        return false;
    return isSame(A.left, B.left) && isSame(A.right, B.right);
}

27. 二叉树的镜像

请完成一个函数，输入一个二叉树，该函数输出它的镜像。

例如输入：

     4
   /   \
  2     7
 / \   / \
1   3 6   9

镜像输出：

     4
   /   \
  7     2
 / \   / \
9   6 3   1

「示例 1：」

输入：root = [4,2,7,1,3,6,9]
输出：[4,7,2,9,6,3,1]

「限制：」

0 <= 节点个数 <= 1000

题目地址：https://leetcode-cn.com/problems/er-cha-shu-de-jing-xiang-lcof/

「解题思路」

我们从根节点开始，递归地对树进行遍历，并从叶子节点先开始翻转得到镜像。如果当前遍历到的节点 root 的左右两棵子树都已经翻转得到镜像，那么我们只需要交换两棵子树的位置，即可得到以 root 为根节点的整棵子树的镜像。

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @return {TreeNode}
 */
var mirrorTree = function(root) {
    if (!root) return null;
    [root.left, root.right] = [root.right, root.left];
    mirrorTree(root.left);
    mirrorTree(root.right);
    return root;
};

28. 对称的二叉树

请实现一个函数，用来判断一棵二叉树是不是对称的。如果一棵二叉树和它的镜像一样，那么它是对称的。

例如，二叉树 [1,2,2,3,4,4,3] 是对称的。

但是下面这个 [1,2,2,null,3,null,3] 则不是镜像对称的:

「示例 1：」

输入：root = [1,2,2,3,4,4,3]
输出：true

「示例 2：」

输入：root = [1,2,2,null,3,null,3]
输出：false

「限制：」

0 <= 节点个数 <= 1000

题目地址：https://leetcode-cn.com/problems/dui-cheng-de-er-cha-shu-lcof/

「解题思路」

对称二叉树定义：对于树中任意两个对称节点 L 和 R ，一定有：
- L.val = R.val ：即此两对称节点值相等。L.left.val = R.right.val ：即 L 的左子节点和 R 的右子节点对称；L.right.val = R.left.val ：即 L 的右子节点和 R 的左子节点对称。
根据以上规律，考虑从顶至底递归，判断每对节点是否对称，从而判断树是否为对称二叉树。

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @return {boolean}
 */
var isSymmetric = function(root) {
    return root === null || isSame(root.left, root.right);
};

function isSame(left, right) {
    if (left === null && right === null) return true;
    if ((!left && right) || (left && !right)) return false;
    return left.val === right.val && isSame(left.left, right.right) && isSame(left.right, right.left);
}

32 - II. 从上到下打印二叉树 II

从上到下按层打印二叉树，同一层的节点按从左到右的顺序打印，每一层打印到一行。

例如: 给定二叉树: [3,9,20,null,null,15,7],

返回其层次遍历结果：

[
  [3],
  [9,20],
  [15,7]
]

「提示：」

节点总数 <= 1000

题目地址：https://leetcode-cn.com/problems/cong-shang-dao-xia-da-yin-er-cha-shu-ii-lcof/

「解题思路」

「按层打印」：题目要求的二叉树的从上至下打印（即按层打印），又称为二叉树的 「s」（BFS）。BFS 通常借助队列的先入先出特性来实现。
「每层打印到一行」：将本层全部节点打印到一行，并将下一层全部节点加入队列，以此类推，即可分为多行打印。

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number[][]}
 */
var levelOrder = function(root) {
    if (!root) return [];
    const result = [[root.val]];
    let node = root;
    const queue = [root];
    while(queue.length) {
        const s = [], res = [];
        while(queue.length) {
            node = queue.shift();
            if (node.left) {
                s.push(node.left);
                res.push(node.left.val);
            }
            if (node.right) {
                s.push(node.right);
                res.push(node.right.val);
            }
        }
        if (res.length) {
            result.push(res);
            queue.push(...s);
        }
    }
    return result;
};

32 - III. 从上到下打印二叉树 III

请实现一个函数按照之字形顺序打印二叉树，即第一行按照从左到右的顺序打印，第二层按照从右到左的顺序打印，第三行再按照从左到右的顺序打印，其他行以此类推。

例如: 给定二叉树: [3,9,20,null,null,15,7],

返回其层次遍历结果：

[
  [3],
  [20,9],
  [15,7]
]

「提示：」

节点总数 <= 1000

题目地址：https://leetcode-cn.com/problems/cong-shang-dao-xia-da-yin-er-cha-shu-iii-lcof/

「解题思路」

在上题「32 - II. 从上到下打印二叉树 II」的基础上修改即可

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number[][]}
 */
var levelOrder = function(root) {
    if (!root) return [];
    const result = [[root.val]];
    let node = root;
    const queue = [root];
    while(queue.length) {
        const s = [], res = [];
        while(queue.length) {
            node = queue.shift();
            if (node.left) {
                s.push(node.left);
                res.push(node.left.val);
            }
            if (node.right) {
                s.push(node.right);
                res.push(node.right.val);
            }
        }
        if (res.length) {
            result.push(result.length % 2 ? res.reverse() : res);
            queue.push(...s);
        }
    }
    return result;
};

33. 二叉搜索树的后序遍历序列

输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历结果。如果是则返回 true，否则返回 false。假设输入的数组的任意两个数字都互不相同。

参考以下这颗二叉搜索树：

「示例 1：」

输入: [1,6,3,2,5]
输出: false

「示例 2：」

输入: [1,3,2,6,5]
输出: true

「提示：」

数组长度 <= 1000

题目地址：https://leetcode-cn.com/problems/er-cha-sou-suo-shu-de-hou-xu-bian-li-xu-lie-lcof/

「解题思路」

二叉搜索树一个特性就是：左子树比根节点小，右子树比根节点大
只要找到左右子树的分界点，然后递归的去判定就好了
中途有任何不满足的就直接返回false就ok

/**
 * @param {number[]} postorder
 * @return {boolean}
 */
var verifyPostorder = function(postorder) {
    function verify(start, end) {
        if (start > end) return true;
        let mid1 = start;
        while(postorder[mid1] < postorder[end]) {
            mid1 ++;
        }
        let mid2 = end - 1;
        while(postorder[mid2] > postorder[end]) {
            mid2 --;
        }
        return  mid1 - 1 === mid2 && verify(start, mid1 - 1) && verify(mid1, end - 1);
    }
    return verify(0, postorder.length - 1);
};

34. 二叉树中和为某一值的路径

给你二叉树的根节点 root 和一个整数目标和 targetSum ，找出所有从根节点到叶子节点路径总和等于给定目标和的路径。

叶子节点是指没有子节点的节点。

「示例 1：」

image-20220228154909908

输入：root = [5,4,8,11,null,13,4,7,2,null,null,5,1], targetSum = 22
输出：[[5,4,11,2],[5,8,4,5]]

「示例 2：」

image-20220228154944915

输入：root = [1,2,3], targetSum = 5
输出：[]

「示例 3：」

输入：root = [1,2], targetSum = 0
输出：[]

「提示：」

树中节点总数在范围 [0, 5000] 内
-1000 <= Node.val <= 1000
-1000 <= targetSum <= 1000

题目地址：https://leetcode-cn.com/problems/er-cha-shu-zhong-he-wei-mou-yi-zhi-de-lu-jing-lcof/

「解题思路」

「深度优先遍历」

每层都三个参数，一个是当前结点，一个是 target 剩余值，一个是总路径数组
当往二叉树深处进行遍历时，如果 target 剩余值跟结点值相等且左右子树为空(叶子结点)，则满足要求，往 result 压入当前总路径数组 path
对于左右子树不为空的结点，继续往左或右子树进行遍历，直到叶子结点

/**
 * 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} target
 * @return {number[][]}
 */
var pathSum = function(root, target) {
    if (!root) return [];
    const res = [];

    const dfs = (root, sum, path) => {
      if(!root) return;
      // 到了叶子节点并且当前节点的值跟剩余sum相等，则推入结果集中
      if (root.val === sum && !root.left && !root.right) {
        res.push(path);
      }
      // 路径中加入当前节点的值
      path.push(root.val);
      dfs(root.left, sum - root.val, path.slice());
      dfs(root.right, sum - root.val, path.slice());
    };
    
    dfs(root, target, []);
    return res;

};

36. 二叉搜索树与双向链表

输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的循环双向链表。要求不能创建任何新的节点，只能调整树中节点指针的指向。

为了让您更好地理解问题，以下面的二叉搜索树为例：

image-20220225152820584

我们希望将这个二叉搜索树转化为双向循环链表。链表中的每个节点都有一个前驱和后继指针。对于双向循环链表，第一个节点的前驱是最后一个节点，最后一个节点的后继是第一个节点。

下图展示了上面的二叉搜索树转化成的链表。“head” 表示指向链表中有最小元素的节点。

image-20220225152834621

特别地，我们希望可以就地完成转换操作。当转化完成以后，树中节点的左指针需要指向前驱，树中节点的右指针需要指向后继。还需要返回链表中的第一个节点的指针。

题目地址：https://leetcode-cn.com/problems/er-cha-sou-suo-shu-yu-shuang-xiang-lian-biao-lcof/

「解题思路」

二叉搜索树的中序遍历便是升序的，自然而然的，我们便先中序遍历将节点保存下来，然后将他们相连成循环双向链表。

/**
 * // Definition for a Node.
 * function Node(val,left,right) {
 *    this.val = val;
 *    this.left = left;
 *    this.right = right;
 * };
 */
/**
 * @param {Node} root
 * @return {Node}
 */
var treeToDoublyList = function(root) {
    if (root === null) return null; 
    const stk = [], nodeList = [];
    let node = root;
    while(stk.length || node) {
        while(node) {
            stk.push(node);
            node = node.left;
        }
        node = stk.pop();
        nodeList.push(node);
        node = node.right;
    }
    nodeList.push(nodeList[0]);
    for(let i = 1; i < nodeList.length - 1; i++) {
        nodeList[i].right = nodeList[i + 1];
        nodeList[i].left = nodeList[i - 1];
    }

    nodeList[0].right = nodeList[1];
    nodeList[0].left = nodeList[nodeList.length - 2];
    return nodeList[0];

};

54. 二叉搜索树的第k大节点

给定一棵二叉搜索树，请找出其中第 k 大的节点的值。

「示例 1:」

输入: root = [3,1,4,null,2], k = 1
   3
  / \
 1   4
  \
   2
输出: 4

「示例 2:」

输入: root = [5,3,6,2,4,null,null,1], k = 3
       5
      / \
     3   6
    / \
   2   4
  /
 1
输出: 4

「限制：」

1 ≤ k ≤ 二叉搜索树元素个数

题目地址：https://leetcode-cn.com/problems/er-cha-sou-suo-shu-de-di-kda-jie-dian-lcof/

「解题思路」

通过逆中序遍历遍历即可

「递归解法」

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @param {number} k
 * @return {number}
 */
var kthLargest = function (root, k) {
  let node;
  if (!root) return node;
  const dfs = (root) => {
    if (!root) return null;
    dfs(root.right);
    k--;
    if (!k) return (node = root.val);
    dfs(root.left);
  };
  dfs(root);
  return node;
};

「非递归解法」

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @param {number} k
 * @return {number}
 */
var kthLargest = function(root, k) {
    const stack = [];
    let node = root;
    while(node || stack.length) {
        while(node) {
            stack.push(node);
            node = node.right;
        }
        node = stack.pop();
        k --;
        if (!k) return node.val;
        node = node.left;
    }
};

55 - I. 二叉树的深度

输入一棵二叉树的根节点，求该树的深度。从根节点到叶节点依次经过的节点（含根、叶节点）形成树的一条路径，最长路径的长度为树的深度。

例如：

给定二叉树 [3,9,20,null,null,15,7]，

返回它的最大深度 3 。

「提示：」

节点总数 <= 10000

题目地址：https://leetcode-cn.com/problems/er-cha-shu-de-shen-du-lcof/

「解题思路」

递归的终止条件是遍历到叶子结点
递归的返回值是左子树深度和右子树深度更大的那个 + 1(因为左右子树有个共同父亲，所以深度上得再加个1)

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number}
 */
var maxDepth = function(root) {
    if (!root) return 0;
    return Math.max(maxDepth(root.left), maxDepth(root.right)) + 1;
};

55 - II. 平衡二叉树

输入一棵二叉树的根节点，判断该树是不是平衡二叉树。如果某二叉树中任意节点的左右子树的深度相差不超过1，那么它就是一棵平衡二叉树。

「示例 1:」

给定二叉树 [3,9,20,null,null,15,7]

返回 true 。

「示例 2:」

给定二叉树 [1,2,2,3,3,null,null,4,4]

返回 false 。

「限制：」

0 <= 树的结点个数 <= 10000

题目地址：https://leetcode-cn.com/problems/ping-heng-er-cha-shu-lcof/

「解题思路」

首先先定义计算节点高度的函数maxDepth(题55 - I. 二叉树的深度)，即可判断二叉树是否平衡。具体做法类似于二叉树的前序遍历，即对于当前遍历到的节点，首先计算左右子树的高度，如果左右子树的高度差是否不超过 1，再分别递归地遍历左右子节点，并判断左子树和右子树是否平衡。这是一个自顶向下的递归的过程。

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @return {boolean}
 */
var isBalanced = function(root) {
    if (!root) return true;
    return Math.abs(maxDepth(root.left) - maxDepth(root.right)) <= 1 && isBalanced(root.left) && isBalanced(root.right);
};

var maxDepth = function(root) {
    if (!root) return 0;
    return Math.max(maxDepth(root.left), maxDepth(root.right)) + 1;
};

68 - I. 二叉搜索树的最近公共祖先

给定一个二叉搜索树, 找到该树中两个指定节点的最近公共祖先。

百度百科中最近公共祖先的定义为：“对于有根树 T 的两个结点 p、q，最近公共祖先表示为一个结点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（「一个节点也可以是它自己的祖先」）。”

例如，给定如下二叉搜索树: root = [6,2,8,0,4,7,9,null,null,3,5]

image-20220301123336763

「示例 1:」

输入: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 8
输出: 6 
解释: 节点 2 和节点 8 的最近公共祖先是 6。

「示例 2:」

输入: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 4
输出: 2
解释: 节点 2 和节点 4 的最近公共祖先是 2, 因为根据定义最近公共祖先节点可以为节点本身。

「说明:」

所有节点的值都是唯一的。
p、q 为不同节点且均存在于给定的二叉搜索树中。

题目地址：https://leetcode-cn.com/problems/er-cha-sou-suo-shu-de-zui-jin-gong-gong-zu-xian-lcof/

「解题思路」

「祖先的定义：」 若节点 p 在节点 root 的左（右）子树中，或 p = root，则称 root 是 p 的祖先。

「最近公共祖先的定义」：设节点 root 为节点 p,q 的某公共祖先，若其左子节点 root.left和右子节点 root.right 都不是 p,q 的公共祖先，则称 root 是 “最近的公共祖先” 。

根据以上定义，若 root 是 p,q 的最近公共祖先，则只可能为以下情况之一：

p 和 q 在 root 的子树中，且分列 root 的异侧（即分别在左、右子树中）；
p = root，且 q 在 root 的左或右子树中；
q = root，且 p 在 root 的左或右子树中；

本题给定了两个重要条件：① 树为二叉搜索树，② 树的所有节点的值都是唯一的。根据以上条件，可方便地判断 p,q 与 root 的子树关系，即：

若 root.val < p.val ，则 p 在 root 右子树中；
若 root.val > p.val ，则 p 在 root 左子树中；
若 root.val = p.val ，则 p 和 root 指向同一节点。

「方法一：迭代」

「循环搜索」：当节点 root 为空时跳出；
1. 当 p, q都在 root 的 「右子树」 中，则遍历至 root.right ；
2. 否则，当 p, q 都在 root 的 「左子树」 中，则遍历至 root.left ；
3. 否则，说明找到了 「最近公共祖先」 ，跳出。
「返回值」：最近公共祖先 root 。

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @param {TreeNode} p
 * @param {TreeNode} q
 * @return {TreeNode}
 */
var lowestCommonAncestor = function(root, p, q) {
    while(root) {
        if (root.val > p.val && root.val > q.val) {
            root = root.left;
        } else if (root.val < p.val && root.val < q.val) {
            root = root.right;
        } else {
            return root;
        }
    }
};

优化：若可保证 p*.val<q.*val ，则在循环中可减少判断条件。

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @param {TreeNode} p
 * @param {TreeNode} q
 * @return {TreeNode}
 */
var lowestCommonAncestor = function(root, p, q) {
    if (p.val > q.val) {
        [p, q] = [q, p];
    }
    while(root) {
        if (root.val > q.val) {
            root = root.left;
        } else if (root.val < p.val) {
            root = root.right;
        } else {
            return root;
        }
    }
};

「方法二：递归」

「递推工作」：
1. 当 p, q 都在 root 的 「右子树」 中，则开启递归 root.right 并返回；
2. 否则，当 p, q 都在 root 的 「左子树」 中，则开启递归 root.left 并返回；
「返回值」：最近公共祖先 root 。

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @param {TreeNode} p
 * @param {TreeNode} q
 * @return {TreeNode}
 */
var lowestCommonAncestor = function(root, p, q) {
    while(root) {
        if (root.val > p.val && root.val > q.val) {
            return lowestCommonAncestor(root.left, p, q);
        } else if (root.val < p.val && root.val < q.val) {
            return lowestCommonAncestor(root.right, p, q);
        } else {
            return root;
        }
    }
};

68 - II. 二叉树的最近公共祖先

给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。

百度百科中最近公共祖先的定义为：“对于有根树 T 的两个结点 p、q，最近公共祖先表示为一个结点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”

例如，给定如下二叉树: root = [3,5,1,6,2,0,8,null,null,7,4]

image-20220301142043674

「示例 1:」

输入: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1
输出: 3
解释: 节点 5 和节点 1 的最近公共祖先是节点 3。

「示例 2:」

输入: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4
输出: 5
解释: 节点 5 和节点 4 的最近公共祖先是节点 5。因为根据定义最近公共祖先节点可以为节点本身。

「说明:」

所有节点的值都是唯一的。
p、q 为不同节点且均存在于给定的二叉树中。

题目地址：https://leetcode-cn.com/problems/er-cha-shu-de-zui-jin-gong-gong-zu-xian-lcof/

「解题思路」

先给出递归函数的定义：给该函数输入三个参数 root，p，q，它会返回一个节点
1. 如果 p 和 q 都在以 root 为根的树中，函数返回的就是 p 和 q 的最近公共祖先节点。
2. 那如果 p 和 q 都不在以 root 为根的树中怎么办呢？函数理所当然地返回 null 呗。
3. 那如果 p 和 q 只有一个存在于 root 为根的树中呢？函数就会返回那个节点。
根据这个定义，分情况讨论：
1. 如果 p 和 q 都在以 root 为根的树中，那么 left 和 right 一定分别是 p 和 q（从 base case 看出来的）。
2. 如果 p 和 q 都不在以 root 为根的树中，直接返回 null。
3. 如果 p 和 q 只有一个存在于 root 为根的树中，函数返回该节点。

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @param {TreeNode} p
 * @param {TreeNode} q
 * @return {TreeNode}
 */
var lowestCommonAncestor = function(root, p, q) {
     // 遇到null，返回null 没有LCA
  if (root == null) return null;
  // 遇到p或q，直接返回当前节点
  if (root == q || root == p) return root;
  // 非null 非q 非p，则递归左右子树
  const left = lowestCommonAncestor(root.left, p, q);
  const right = lowestCommonAncestor(root.right, p, q);
  // 根据递归的结果，决定谁是LCA
  if (left && right) return root;
  if (left == null && right == null) return null;
  return left == null ? right : left;
};

面试题32 - I. 从上到下打印二叉树

从上到下打印出二叉树的每个节点，同一层的节点按照从左到右的顺序打印。

例如: 给定二叉树: [3,9,20,null,null,15,7],

[3,9,20,15,7]

「提示：」

节点总数 <= 1000

题目地址：https://leetcode-cn.com/problems/cong-shang-dao-xia-da-yin-er-cha-shu-lcof/

「解题思路」

题目要求的二叉树的 「从上至下」 打印（即按层打印），又称为二叉树的 「广度优先搜索」（BFS）。
BFS 通常借助 「队列」 的先入先出特性来实现。

「特例处理」：当树的根节点为空，则直接返回空列表 [] ；
「初始化」：打印结果列表 result = [] ，包含根节点的队列 queue = [root] ；
「BFS 循环」：当队列 queue 为空时跳出；
1. 「出队」：队首元素出队，记为 node；
2. 「打印」：将 node.val 添加至列表尾部；
3. 「添加子节点」：若 node 的左（右）子节点不为空，则将左（右）子节点加入队列 queue ；
「返回值」：返回打印结果列表 result 即可。

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number[]}
 */
var levelOrder = function(root) {
    if (!root) return []; 
    const queue = [root], result = [];
    while(queue.length) {
        const node = queue.shift();
        result.push(node.val);
        if (node.left) {
            queue.push(node.left);
        }
        if (node.right) {
            queue.push(node.right);
        }
    }
    return result;
};

本文参与腾讯云自媒体同步曝光计划，分享自微信公众号。

原始发表：2022-03-01，如有侵权请联系 cloudcommunity@tencent.com 删除

二叉树