DEV Community 👩‍💻👨‍💻

Cover image for 代码随想录day21 | 530. Minimum Absolute Difference in BST, 501. Find Mode in BST, 236. Lowest Common Ancestor of a Binary Tree
Ming
Ming

Posted on

代码随想录day21 | 530. Minimum Absolute Difference in BST, 501. Find Mode in BST, 236. Lowest Common Ancestor of a Binary Tree

leetcode 530 - Minimum Absolute Difference in BST

给你一棵所有节点为非负值的二叉搜索树,请你计算树中任意两节点的差的绝对值的最小值, 提示:树中至少有 2 个节点。

Image description

最直观的想法,就是把BST通过inorder dfs recursion转换成有序数组,然后遍历一遍数组,就统计出来最小差值了(solution1), 第二个解法也是基于inorder dfs recursion, 但是不用开辟数组,可以直接在递归里maintain结果变量(solution2). 这道题也是lc98的变形题

//👍 Solution 1: bst dfs inorder to create visited array, then find the Minimum Diff of that array 

var getMinimumDifference = function (root) {
  const visited = [];

  const helper = (node) => {
    if (!node) return;

    if (node.left) helper(node.left);
    visited.push(node.val);
    if (node.right) helper(node.right);
  };

  helper(root);

  let minAbsDiff = Infinity;
  for (let i = 0; i < visited.length; i++) {
    const diff = Math.abs(visited[i] - visited[i + 1]);
    if (diff < minAbsDiff) {
      minAbsDiff = diff;
    }
  }

  return minAbsDiff;
};

Enter fullscreen mode Exit fullscreen mode
//👍👍 Solution 2: bst dfs inorder, but no need to create array!

var getMinimumDifference = function (root) {
  let pre = null;
  let minDiff = Infinity;

  const helper = (node) => {
    if (!node) return;

    if (node.left) helper(node.left);
    if (pre) {
      const currDiff = Math.abs(pre.val - node.val);
      minDiff = Math.min(minDiff, currDiff);
    }
    pre = node;
    if (node.right) helper(node.right);
  };

  helper(root);
  return minDiff;
};

Enter fullscreen mode Exit fullscreen mode

leetcode 501 - Find Mode in Binary Search Tree

给定一个有相同值的二叉搜索树(BST),找出 BST 中的所有众数(出现频率最高的元素.

假定 BST 有如下定义:
结点左子树中所含结点的值小于等于当前结点的值
结点右子树中所含结点的值大于等于当前结点的值
左子树和右子树都是二叉搜索树

example:
Image description

最直观的方法是把这个树都遍历了,用map统计频率,把频率排个序,最后取前面高频的元素的集合(solution1), 第二个解法利用了bst特性,既然是搜索树,它中序遍历就是有序的,遍历有序数组的元素出现频率,从头遍历,那么一定是相邻两个元素作比较,然后就把出现频率最高的元素输出就可以了。

//👍 Solution 1: dfs inorder to create visited map, then find the most high frequency of that map

var findMode = function (root) {
  const map = new Map();

  const helper = (node) => {
    if (!node) return;

    if (node.left) helper(node.left);
    map.set(node.val, map.get(node.val) + 1 || 1);
    if (node.right) helper(node.right);
  };
  helper(root);

  let maxCount = map.get(root.val);
  let result = [];
  for (let [key, value] of map) {
    if (value === maxCount) {
      result.push(key);
    }
    if (value > maxCount) {
      result = [];
      maxCount = value;
      result.push(key);
    }
  }

  return result;
};
Enter fullscreen mode Exit fullscreen mode
//👍👍 Solution 2: dfs inorder, but no need to create map!

var findMode = function (root) {
  let result = [];
  let pre = null;
  let count = 0; // 记录单个元素出现的频率
  let maxCount = 1; // 记录整个树中某元素出现的最大频率

  const helper = (node) => {
    if (!node) return;

    helper(node.left);

    if (!pre) count = 1; // 第一个节点
    else if (pre && node.val === pre.val) count++; // 与前一个节点数值相同
    else count = 1; // 与前一个节点数值不同
    pre = node; // 更新上一个节点
    if (count === maxCount) {
      // 如果和最大值相同,放进result中
      result.push(node.val);
    } else if (count > maxCount) {
      // 如果计数大于最大值频率,要更新最大频率,要清空result,因为之前result里的元素都失效了, 最后更新result
      maxCount = count;
      result = [];
      result.push(node.val);
    }

    helper(node.right);
  };

  helper(root);
  return result;
};

Enter fullscreen mode Exit fullscreen mode

leetcode 236 - Lowest Common Ancestor of a Binary Tree

给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。
最近公共祖先的定义为:“对于有根树 T 的两个结点 p、q,最近公共祖先表示为一个结点 x,满足 x 是 p、q 的祖先且 x 的深度尽可能大(一个节点也可以是它自己的祖先)。”

Image description

遇到这个题目首先想的是要是能自底向上查找就好了,这样就可以找到公共祖先了。那么二叉树如何可以自底向上查找呢?回溯啊,二叉树回溯的过程就是从底到上。后序post_order遍历(左右中)就是天然的回溯过程,可以根据左右子树的返回值,来处理中节点的逻辑, 最后通过回溯将结果返回给头结点

这道题目刷过的同学未必真正了解这里面回溯的过程,以及结果是如何一层一层传上去的。
那么我给大家归纳如下三点:

  • 求最小公共祖先,需要从底向上遍历,那么二叉树,只能通过后序遍历(即:回溯)实现从低向上的遍历方式。
  • 在回溯的过程中,必然要遍历整棵二叉树,即使已经找到结果了,依然要把其他节点遍历完,因为要使用递归函数的返回值(也就是代码中的left和right)做逻辑判断。
  • 要理解如果返回值left为空,right不为空为什么要返回right,为什么可以用返回right传给上一层结果。
  • 可以说这里每一步,都是有难度的,都需要对二叉树,递归和回溯有一定的理解。 本题没有给出迭代法,因为迭代法不适合模拟回溯的过程。理解递归的解法就够了。

今日学习文章

/* 👍👍 使用recursuib的方法, 需要从下到上,所以使用post order: */

var lowestCommonAncestor = function (root, p, q) {

  const travelTree = function (node, p, q) {
    // 确定递归终止条件
    if (!node) return null;
    if (node === p || node === q) return node; // find the p or q node, then return this p or q

    let left = travelTree(node.left, p, q);
    let right = travelTree(node.right, p, q);
    if (left && right) return root; //如果left和right都不为空,说明此时root就是最近公共节点。
    if (!left) return right; //如果left为空,right不为空,就返回right,说明目标节点是通过right返回的,反之依然
    return left;
  };
  return travelTree(root, p, q);
};

Enter fullscreen mode Exit fullscreen mode

学习总结:

  1. BST常用in-order dfs
  2. 寻找公共祖先要用post-order dfs

Top comments (0)

Tired of sifting through your feed?

You can change your feed and see more relevant posts by adding a rating to different tags on DEV. Head here to adjust your weights.