二叉树的属性 | Alvin's note

对称二叉树

leetcode: 给你一个二叉树的根节点 root，检查它是否轴对称。

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

code:

/**
 * @param {TreeNode} root
 * @return {boolean}
 */
var isSymmetric = function (root) {
  const check = (left, right) => {
    if (!left && !right) return true; // 左右子树都不存在 也是对称的
    if (left && right) {
      // 左右子树都存在，要继续判断
      return (
        left.val === right.val && // 左右子树的顶点值要相等
        check(left.left, right.right) && // 左子树的left和右子树的right相等
        check(left.right, right.left) // 左子树的right和右子树的left相等
      );
    }
    // 左右子树中的一个不存在，一个存在，不是对称的
    return false;
  };
  return !root || check(root.left, root.right); // root为null也是对称的
};

二叉树的最大深度

leetcode：给定一个二叉树，找出其最大深度。

二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。

说明: 叶子节点是指没有子节点的节点。

我的答案：

var maxDepth = function (root) {
  let deep = 0;
  function dfs(node, len) {
    if (node) {
      deep = Math.max(deep, len + 1);
      node.left && dfs(node.left, len + 1);
      node.right && dfs(node.right, len + 1);
    }
  }

  dfs(root, 0);
  return deep;
};

别人的答案：

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

二叉树的最小深度

leetcode：给定一个二叉树，找出其最小深度。

最小深度是从根节点到最近叶子节点的最短路径上的节点数量。

说明：叶子节点是指没有子节点的节点。

/**
 * @param {TreeNode} root
 * @return {number}
 */
var minDepth = function (root) {
  if (!root) return 0;
  // 到叶子节点 返回 1 终止条件！
  if (!root.left && !root.right) return 1;
  // 只有右节点时 递归右节点
  if (!root.left) return 1 + minDepth(root.right);
  // 只有左节点时 递归左节点
  if (!root.right) return 1 + minDepth(root.left);
  return Math.min(minDepth(root.left), minDepth(root.right)) + 1;
};

平衡二叉树

leetcode：给定一个二叉树，判断它是否是高度平衡的二叉树。

本题中，一棵高度平衡二叉树定义为：

一个二叉树每个节点的左右两个子树的高度差的绝对值不超过 1 。

true

false

/**
 * @param {TreeNode} root
 * @return {boolean}
 */
var isBalanced = function (root) {
  if (!root) return true;
  if (Math.abs(getDeep(root.left) - getDeep(root.right)) > 1) return false;
  return isBalanced(root.left) && isBalanced(root.right);
};

function getDeep(node) {
  if (!node) return 0;
  return 1 + Math.max(getDeep(node.left), getDeep(node.right));
}

完全二叉树的节点个数

其实就是计算有多少个节点

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

/**
 * @param {TreeNode} root
 * @return {number}
 */
var countNodes = function (root) {
  function dfs(node) {
    if (!node) return 0;
    return 1 + dfs(node.left) + dfs(node.right);
  }
  return dfs(root);
};

二叉树的所有路径

给你一个二叉树的根节点 root ，按任意顺序，返回所有从根节点到叶子节点的路径。

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

输入：root = [1,2,3,null,5]
输出：["1->2->5","1->3"]

显而易见，深度优先遍历啦

/**
 * @param {TreeNode} root
 * @return {string[]}
 */
var binaryTreePaths = function (root) {
  let result = [];
  function dfs(node, path = []) {
    if (!node) return;
    if (!node.left && !node.right) {
      result.push([...path, node.val].join('->'));
    } else {
      dfs(node.left, [...path, node.val]);
      dfs(node.right, [...path, node.val]);
    }
  }

  dfs(root);
  return result;
};

左叶子之和

给定二叉树的根节点 root ，返回所有左叶子之和。

输入: root = [3,9,20,null,null,15,7]
输出: 24
解释: 在这个二叉树中，有两个左叶子，分别是 9 和 15，所以返回 24

也是 dfs，比较简单

/**
 * @param {TreeNode} root
 * @return {number}
 */
var sumOfLeftLeaves = function (root) {
  // 左叶子
  // !node.left && !node.right && parent.left === node;
  let sum = 0;
  function dfs(node, parent) {
    if (!node) return;
    if (parent && parent.left === node && !node.left && !node.right) sum += node.val;
    dfs(node.left, node);
    dfs(node.right, node);
  }
  dfs(root);
  return sum;
};

找树左下角的值

给定一个二叉树的 根节点 root，请找出该二叉树的 最底层最左边 节点的值。

假设二叉树中至少有一个节点。

输入: root = [2, 1, 3];
输出: 1;

我这里第一步思路是通过 bfs 做的，关于层序遍历可以看二叉树的层序遍历

二维数组最后一个序号，第一个数就是最左的叶子 🍃！

/**
 * @param {TreeNode} root
 * @return {number}
 */
var findBottomLeftValue = function (root) {
  let queue = [root]; // 至少有一个节点
  let bfsResult = [];
  while (queue.length) {
    let len = queue.length;
    let temp = [];
    for (let i = 0; i < len; i++) {
      const node = queue.shift();
      temp.push(node.val);
      node.left && queue.push(node.left);
      node.right && queue.push(node.right);
    }
    bfsResult.push(temp);
  }

  return bfsResult[bfsResult.length - 1][0];
};

dfs 解法

var findBottomLeftValue = function (root) {
  let res;
  let maxDepth = 0;
  function dfs(node, deepth = 1) {
    if (!node) return;
    if (!node.left && !node.right) {
      if (deepth > maxDepth) {
        res = node.val;
        maxDepth = deepth;
      }
    }
    dfs(node.left, deepth + 1);
    dfs(node.right, deepth + 1);
  }
  dfs(root);
  return res;
};

路径总和

leetcode给你二叉树的根节点 root 和一个表示目标和的整数 targetSum 。判断该树中是否存在根节点到叶子节点的路径，这条路径上所有节点值相加等于目标和 targetSum 。如果存在，返回 true ；否则，返回 false 。

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

输入：root = [5,4,8,11,null,13,4,7,2,null,null,null,1], targetSum = 22
输出：true
解释：等于目标和的根节点到叶节点路径如上图所示。

输入：root = [1,2,3], targetSum = 5
输出：false
解释：树中存在两条根节点到叶子节点的路径：
(1 --> 2): 和为 3
(1 --> 3): 和为 4
不存在 sum = 5 的根节点到叶子节点的路径。

输入：root = [], targetSum = 0
输出：false
解释：由于树是空的，所以不存在根节点到叶子节点的路径。

dfs 递归搞定

var hasPathSum = function (root, targetSum) {
  if (!root) return false;
  if (!root.left && !root.right && root.val === targetSum) return true;
  return hasPathSum(root.left, targetSum - root.val) || hasPathSum(root.right, targetSum - root.val);
};

对称二叉树 ​

二叉树的最大深度 ​

二叉树的最小深度 ​

平衡二叉树 ​

完全二叉树的节点个数 ​

二叉树的所有路径 ​

左叶子之和 ​

找树左下角的值 ​

路径总和 ​