《剑指 Offer(第 2 版)》树部分JavaScript题解

2022-10-24 18:47:48 浏览数 (1)

《剑指 Offer (第 2 版)》树部分 JavaScript 题解

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

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

07. 重建二叉树

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

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

「示例 1:」

代码语言:javascript复制
Input: preorder = [3,9,20,15,7], inorder = [9,3,15,20,7]
Output: [3,9,20,null,null,15,7]

「示例 2:」

代码语言:javascript复制
Input: preorder = [-1], inorder = [-1]
Output: [-1]

「限制:」

  • 0 <= 节点个数 <= 5000

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

「解题思路」

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

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

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

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

代码语言:javascript复制
/**
 * 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:

代码语言:javascript复制
     3
    / 
   4   5
  / 
 1   2

给定的树 B:

代码语言:javascript复制
   4 
  /
 1

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

「示例 1:」

代码语言:javascript复制
输入:A = [1,2,3], B = [3,1]
输出:false

「示例 2:」

代码语言:javascript复制
输入: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空了,说明不是子树;然后判断值;最后继续递归各自左子树、右子树。
代码语言:javascript复制
/**
 * 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. 二叉树的镜像

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

例如输入:

代码语言:javascript复制
     4
   /   
  2     7
 /    / 
1   3 6   9

镜像输出:

代码语言:javascript复制
     4
   /   
  7     2
 /    / 
9   6 3   1

「示例 1:」

代码语言:javascript复制
输入: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 为根节点的整棵子树的镜像。

代码语言:javascript复制
/**
 * 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] 是对称的。

代码语言:javascript复制
    1
   / 
  2   2
 /  / 
3  4 4  3

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

代码语言:javascript复制
    1
   / 
  2   2
      
   3    3

「示例 1:」

代码语言:javascript复制
输入:root = [1,2,2,3,4,4,3]
输出:true

「示例 2:」

代码语言:javascript复制
输入: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 的 左子节点 对称。
  • 根据以上规律,考虑从顶至底递归,判断每对节点是否对称,从而判断树是否为对称二叉树。
代码语言:javascript复制
/**
 * 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],

代码语言:javascript复制
    3
   / 
  9  20
    /  
   15   7

返回其层次遍历结果:

代码语言:javascript复制
[
  [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 通常借助 队列 的先入先出特性来实现。
  • 「每层打印到一行」:将本层全部节点打印到一行,并将下一层全部节点加入队列,以此类推,即可分为多行打印。
代码语言:javascript复制
/**
 * 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],

代码语言:javascript复制
    3
   / 
  9  20
    /  
   15   7

返回其层次遍历结果:

代码语言:javascript复制
[
  [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」的基础上修改即可

代码语言:javascript复制
/**
 * 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。假设输入的数组的任意两个数字都互不相同。

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

代码语言:javascript复制
     5
    / 
   2   6
  / 
 1   3

「示例 1:」

代码语言:javascript复制
输入: [1,6,3,2,5]
输出: false

「示例 2:」

代码语言:javascript复制
输入: [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/

「解题思路」

  • 二叉搜索树一个特性就是:左子树比根节点小,右子树比根节点大
  • 只要找到左右子树的分界点,然后递归的去判定就好了
  • 中途有任何不满足的就直接返回falseok
代码语言:javascript复制
/**
 * @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

代码语言:javascript复制
输入: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

代码语言:javascript复制
输入:root = [1,2,3], targetSum = 5
输出:[]

「示例 3:」

代码语言:javascript复制
输入: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
  • 对于左右子树不为空的结点,继续往左或右子树进行遍历,直到叶子结点
代码语言:javascript复制
/**
 * 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/

「解题思路」

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

代码语言:javascript复制
/**
 * // 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:」

代码语言:javascript复制
输入: root = [3,1,4,null,2], k = 1
   3
  / 
 1   4
  
   2
输出: 4

「示例 2:」

代码语言:javascript复制
输入: 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/

「解题思路」

通过逆中序遍历遍历即可

「递归解法」

代码语言:javascript复制
/**
 * 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;
};

「非递归解法」

代码语言:javascript复制
/**
 * 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],

代码语言:javascript复制
    3
   / 
  9  20
    /  
   15   7

返回它的最大深度 3 。

「提示:」

  • 节点总数 <= 10000

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

「解题思路」

  • 递归的终止条件是遍历到叶子结点
  • 递归的返回值是 左子树深度 和 右子树深度 更大的那个 1(因为左右子树有个共同父亲,所以深度上得再加个1)
代码语言:javascript复制
/**
 * 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]

代码语言:javascript复制
    3
   / 
  9  20
    /  
   15   7

返回 true

「示例 2:」

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

代码语言:javascript复制
       1
      / 
     2   2
    / 
   3   3
  / 
 4   4

返回 false

「限制:」

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

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

「解题思路」

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

代码语言:javascript复制
/**
 * 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:」

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

「示例 2:」

代码语言:javascript复制
输入: 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 的 最近公共祖先 ,则只可能为以下情况之一:

  1. p 和 q 在 root 的子树中,且分列 root 的 异侧(即分别在左、右子树中);
  2. p = root,且 q 在 root 的左或右子树中;
  3. 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 指向 同一节点 。

「方法一:迭代」

  1. 「循环搜索」:当节点 root 为空时跳出;
    1. 当 p, q都在 root 的 「右子树」 中,则遍历至 root.right ;
    2. 否则,当 p, q 都在 root 的 「左子树」 中,则遍历至 root.left ;
    3. 否则,说明找到了 「最近公共祖先」 ,跳出。
  2. 「返回值」:最近公共祖先 root 。
代码语言:javascript复制
/**
 * 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 ,则在循环中可减少判断条件。

代码语言:javascript复制
/**
 * 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. 「递推工作」
    1. 当 p, q 都在 root 的 「右子树」 中,则开启递归 root.right 并返回;
    2. 否则,当 p, q 都在 root 的 「左子树」 中,则开启递归 root.left 并返回;
  2. 「返回值」:最近公共祖先 root 。
代码语言:javascript复制
/**
 * 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:」

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

「示例 2:」

代码语言:javascript复制
输入: 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/

「解题思路」

  1. 先给出递归函数的定义:给该函数输入三个参数 root,p,q,它会返回一个节点
    1. 如果 p 和 q 都在以 root 为根的树中,函数返回的就是 p 和 q 的最近公共祖先节点。
    2. 那如果 p 和 q 都不在以 root 为根的树中怎么办呢?函数理所当然地返回 null 呗。
    3. 那如果 p 和 q 只有一个存在于 root 为根的树中呢?函数就会返回那个节点。
  2. 根据这个定义,分情况讨论:
    1. 如果 p 和 q 都在以 root 为根的树中,那么 left 和 right 一定分别是 p 和 q(从 base case 看出来的)。
    2. 如果 p 和 q 都不在以 root 为根的树中,直接返回 null。
    3. 如果 p 和 q 只有一个存在于 root 为根的树中,函数返回该节点。
代码语言:javascript复制
/**
 * 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],

代码语言:javascript复制
    3
   / 
  9  20
    /  
   15   7

返回:

代码语言:javascript复制
[3,9,20,15,7]

「提示:」

  • 节点总数 <= 1000

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

「解题思路」

  • 题目要求的二叉树的 「从上至下」 打印(即按层打印),又称为二叉树的 「广度优先搜索」(BFS)。
  • BFS 通常借助 「队列」 的先入先出特性来实现。
  1. 「特例处理」:当树的根节点为空,则直接返回空列表 []
  2. 「初始化」:打印结果列表 result = [] ,包含根节点的队列 queue = [root]
  3. 「BFS 循环」:当队列 queue 为空时跳出;
    1. 「出队」:队首元素出队,记为 node
    2. 「打印」:将 node.val 添加至列表尾部;
    3. 「添加子节点」:若 node 的左(右)子节点不为空,则将左(右)子节点加入队列 queue
  4. 「返回值」:返回打印结果列表 result 即可。
代码语言:javascript复制
/**
 * 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;
};

0 人点赞