二叉树

二叉树理论基础

二叉树是一种非线性的数据结构，代笔“祖先”和“后代”之间的派生关系，体现了“一分为二”的分治逻辑。与链表类似，二叉树的基本单元是节点，每个节点包含值、左子节点和右子节点的引用。

一个节点类的示例如下：

/**
 * 二叉树节点类
 * val:节点值
 * left:左子节点的引用
 * right:右子节点的引用
 */
class TreeNode {
  constructor(
    public val?: number,
    public left: TreeNode | null = null,
    public right: TreeNode | null = null,
  ) {}
}

每个节点都有两个引用（指针），分别指向左子节点和右子节点，该节点被称为节点的父节点。当给定一个二叉树的节点时，我们将该节点的左子节点及其以下的节点形成的树称为该节点的左子树，同理，将该节点的右子节点及其以下的节点形成的树称为该节点的右子树。

在二叉树中，除了叶节点外，其他所有子节点都包含子节点和非空子树

二叉树的常见术语

• 根节点：位于二叉树顶层的节点，没有父节点。
• 叶节点：没有子节点的节点，其两个指针均指向None。
• 边:连接两个节点的线段，即节点引用（指针）。
• 节点所在的层：从顶层递增，根节点所在的层为1。
• 节点的度：节点的子节点的数量。在二叉树中，度的取值范围是0、1、2。
• 二叉树的高度：从跟节点到最远叶节点所经过的边的数量。
• 节点的深度：从根节点到该节点所经过的边的数量。
• 节点的高度：从距离该节点最远的叶节点到该节点所经过的边的数量。

二叉树的类型

1. 完美二叉树

   完美二叉树所有层的节点都被完全填满，在完美二叉树中，叶节点的度为0，其余所有节点的度都为2，若树的高度为h，则节点总数为

   $$2^{h+1}-1$$

   呈现出指数级关系。

2. 完全二叉树

   只有最底层的节点未被填满，且最底层节点尽量靠右填充。

3. 完满二叉树

   除了叶节点外，其余所有节点都有两个子节点。

4. 平衡二叉树

   平衡二叉树中任意节点的左子树和右子树的感度之差的绝对值不过1。

第一部分（二叉树的遍历）

二叉树的常见遍历方式是：层序遍历、中序遍历、后序遍历等。

层序遍历

从顶部到底层遍历二叉树，并在每一层从左到右顺序访问节点。

层序遍历本质上属于广度优先遍历，也称广度优先搜索，它体现了一种“逐层向外遍历“的方式。

代码示例如下：

/* 层序遍历 */
function levelOrder(root: TreeNode | null): number[] {
    // 初始化队列，加入根节点
    const queue = [root];
    // 初始化一个列表，用于保存遍历序列
    const list: number[] = [];
    while (queue.length) {
        let node = queue.shift() as TreeNode; // 队列出队
        list.push(node.val); // 保存节点值
        if (node.left) {
            queue.push(node.left); // 左子节点入队
        }
        if (node.right) {
            queue.push(node.right); // 右子节点入队
        }
    }
    return list;
}

前序、中序、后序遍历

使用递归函数遍历二叉树需要注意的点：

1. 确定递归函数的参数和返回值
2. 确定终止条件
3. 确定单层递归的逻辑

代码实现：

/**
 * 前序遍历
 * 访问优先级：根节点 -> 左子树 -> 右子树
 * @param root
 * @param list
 * @returns
 */
function preOrder(root: TreeNode | null, list: number[]): number[] {
  if (root === null) return list;
  list.push(root.val!);
  preOrder(root.left, list);
  preOrder(root.right, list);
  return list;
}

/**
 * 中序遍历
 * 访问优先级：左子树 -> 根节点 -> 右子树
 * @param root
 * @param list
 * @returns
 */
function inOrder(root: TreeNode | null, list: number[]): number[] {
  if (root === null) return list;
  inOrder(root.left, list);
  list.push(root.val!);
  inOrder(root.right, list);
  return list;
}

/**
 * 后序遍历
 * 访问优先级：左子树 -> 右子树 -> 根节点
 * @param root
 * @param list
 * @returns
 */
function postOrder(root: TreeNode | null, list: number[]): number[] {
  if (root === null) return list;
  postOrder(root.left, list);
  postOrder(root.right, list);
  list.push(root.val!);
  return list;
}

二叉树的迭代遍历

二叉树迭代遍历是一种不使用递归而是使用栈（或者其他数据结构）来遍历二叉树的方法。常见的二叉树迭代遍历有三种：前序遍历、中序遍历、后序遍历。

前序遍历

代码示例：

function preorderTraversal(root: TreeNode | null): number[] {
  if (!root) return [];

  const stack: TreeNode[] = [root];
  const res: number[] = [];

  while (stack.length > 0) {
    const node = stack.pop()!;
    res.push(node.val!);

    // 注意：先 push 右子树，再 push 左子树
    // 因为栈是后进先出，我们要保证左子树先被处理
    if (node.right) stack.push(node.right);
    if (node.left) stack.push(node.left);
  }

  return res;
}

中序遍历

代码示例：

function inorderTraversal(root: TreeNode | null): number[] {
  const stack: TreeNode[] = [];
  const result: number[] = [];
  let current: TreeNode | null = root;

  while (current || stack.length > 0) {
    while (current) {
      stack.push(current);
      current = current.left;
    }
    current = stack.pop()!;
    result.push(current.val!);
    current = current.right;
  }

  return result;
}

后序遍历

代码示例：

function postorderTraversal(root: TreeNode | null): number[] {
  if (!root) return [];

  const stack: [TreeNode, boolean][] = [[root, false]]; // 栈中存储节点和访问标记
  const result: number[] = [];

  while (stack.length > 0) {
    const [node, visited] = stack.pop()!;

    if (!visited) {
      // 如果节点未访问，则标记为已访问，并将右子节点和左子节点（逆序）入栈
      stack.push([node, true]);
      if (node.right) {
        stack.push([node.right, false]);
      }
      if (node.left) {
        stack.push([node.left, false]);
      }
    } else {
      // 如果节点已访问，则将节点值加入结果集
      result.push(node.val!);
    }
  }
  return result
}

第二部分 练习题

INFO

反转二叉树

反转一颗二叉树。

代码示例：

function invertTree(root: TreeNode | null): TreeNode | null {
  if (!root) return root;

  const swap = (node: TreeNode) => {
    const rightTmp = node.left;
    node.left = node.right;
    node.right = rightTmp;
  };

  const inver = (root: TreeNode | null) => {
    if (!root) return;
    swap(root!);
    inver(root?.left!);
    inver(root?.right!);
  };
  inver(root)
  return root;
}

INFO

对称二叉树

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

代码示例：

function isSymmetric(root: TreeNode | null): boolean {
    function recur(node1: TreeNode | null, node2: TreeNode | null): boolean {
        if (node1 === null && node2 === null) return true;
        if (node1 === null || node2 === null) return false;
        if (node1.val !== node2.val) return false
        let isSym1: boolean = recur(node1.left, node2.right);
        let isSym2: boolean = recur(node1.right, node2.left);
        return isSym1 && isSym2
    }
    if (root === null) return true;
    return recur(root.left, root.right);
};

INFO

二叉树最大深度

给定一个二叉树 root ，返回其最大深度。

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

代码示例：

/**
 * 解体的关键是需要知道：二叉树 的最远子节点到跟节点的距离就是二叉树最大深度
 * @param root as TreeNode
 * @returns 
 */
function maxDepth(root: TreeNode | null): number {
  if (!root) return 0;
  return 1 + Math.max(maxDepth(root.left), maxDepth(root.right));
}

INFO

二叉树最小深度

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

代码示例：

function minDepth(root: TreeNode | null): number {
    if (root === null) return 0;
    if (root.left !== null && root.right === null) {
        return 1 + minDepth(root.left);
    }
    if (root.left === null && root.right !== null) {
        return 1 + minDepth(root.right);
    }
    return 1 + Math.min(minDepth(root.left), minDepth(root.right));
}

第三部分 练习题

INFO

给定一个二叉树，判断它是否是 平衡二叉树

代码示例：

/**
 * 求二叉树是否是平衡二叉树,平衡二叉树的特征是：任意一个节点的左子树的高度和右子树的高度之差不大于1，也就是 <= 1。
 * @param root as TreeNode
 * @returns
 */

function isBalanced(root: TreeNode | null): boolean {
  function getHeight(root: TreeNode | null): number {
    //因为要返回高度，所以当遍历到null时的高度是0
    if (!root) return 0;
    //递归获取左子树和右子树的高度
    let leftHeight = getHeight(root.left),rightHeight = getHeight(root.right);
    //判断是否当前节点的左子树或右子树是否已经不满足平衡二叉树的特征
    if (leftHeight == -1 || rightHeight == -1) return -1;
    let res: number;
    //判断当前节点的左子树和右子树的高度差是否满足平衡二叉树的特征，入不满足，则返回 -1
    if (Math.abs(leftHeight - rightHeight) > 1) return (res = -1);
    else {
      //若满足，返回当前节点的高度
      res = 1 + Math.max(leftHeight, rightHeight);
    }
    return res;
  }
  return getHeight(root) !== -1;
}

INFO

二叉树的所有路径：

给定一个二叉树，返回所有从根节点到叶子节点的路径。

代码示例：

/**
 * 采用前序遍历的方式解题。
 * 在递归的过程中记录递归的路径<path[]>,当递归到左右节点都是null的时候，说明该节点是叶子节点
 * 将path的所有id拼接成字符串：'1'->'2'->'3',加入到result数组中，记录一条路径
 * 在递归结束之后，所有的路径都被记录到result数组
 * @param node
 * @param path
 * @param result
 */
function travel(node: TreeNode, path: number[], result: string[]) {
  //先记录当前节点值，避免出现遗漏最后一个节点的情况
  path.push(node.val)
  //递归到子节点
  if (node.left == null && node.right == null) {
    //记录一条路径
    result.push(path.join('->'))
    return
  }

  //如果存在左子节点，则向左递归
  if (node.left) {
    travel(node.left, path, result)
    //回溯,归的阶段将数组成员依次弹出，有一种往根节点缩的感觉
    path.pop()
  }

  //如果存在右子节点，则向右递归
  if (node.right) {
    travel(node.right, path, result)
    //回溯,归的阶段将数组成员依次弹出，有一种往根节点缩的感觉
    path.pop()
  }
}

function binaryTreePaths(root: TreeNode | null): string[] {
  let result = [] as string[]
  let path = [] as number[]
  travel(root!, path, result)
  return result
}

INFO

计算二叉树的左叶子节点之和

代码示例：

/**
 * 要操作叶子节点，需要在叶子节点的父节点进行操作。如果直接在当前节点进行操作，就不能判断当前节点是否是叶节点
 * @param root
 * @returns
 */
function sumOfLeftLeaves(root: TreeNode | null): number {
  //若遇到空节点或叶节点直接返回，遇到叶节点返回是因为在当前节点不能判断当前叶节点是否是左节点，所以需要在叶节点的父节点进行求和的操作，所以当遇到叶节点直接返回
  if (!root || (root.left == null && root.right == null)) return 0;
  let leftSum = sumOfLeftLeaves(root.left),rightSum = sumOfLeftLeaves(root.right);
  if (root.left != null && root.left.left == null && root.left.right == null) {
    //当前节点位于叶节点的父节点时
    leftSum = root.left.val!;
  }
  return leftSum + rightSum;
}

INFO

计算完全二叉树的节点数量

代码示例：

function countNodes(root: TreeNode | null): number {
  if (root === null) return 0;
  return 1 + countNodes(root.left) + countNodes(root.right);
};

第四部分 练习题

INFO

找树左下角的值

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

代码示例（递归解法）：

function findBottomLeftValue(root: TreeNode | null): number {
    function recur(root: TreeNode, depth: number): void {
        if (root.left === null && root.right === null) {
            if (depth > maxDepth) {
                maxDepth = depth;
                resVal = root.val;
            }
            return;
        }
        if (root.left !== null) recur(root.left, depth + 1);
        if (root.right !== null) recur(root.right, depth + 1);
    }
    let maxDepth: number = 0;
    let resVal: number = 0;
    if (root === null) return resVal;
    recur(root, 1);
    return resVal;
};

代码示例（迭代法）：

function findBottomLeftValue(root: TreeNode | null): number {
    let helperQueue: TreeNode[] = [];
    if (root !== null) helperQueue.push(root);
    let resVal: number = 0;
    let tempNode: TreeNode;
    while (helperQueue.length > 0) {
        resVal = helperQueue[0].val;
        for (let i = 0, length = helperQueue.length; i < length; i++) {
            tempNode = helperQueue.shift()!;
            if (tempNode.left !== null) helperQueue.push(tempNode.left);
            if (tempNode.right !== null) helperQueue.push(tempNode.right);
        }
    }
    return resVal;
};

INFO

路径总和

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

代码示例：

function hasPathSum(root: TreeNode | null, targetSum: number): boolean {
    if (root === null) return false;
    targetSum -= root.val;
    if (
        root.left === null &&
        root.right === null &&
        targetSum === 0
    ) return true;
    return hasPathSum(root.left, targetSum) ||
        hasPathSum(root.right, targetSum);
};

INFO

从中序与后序遍历序列构造二叉树

给定两个整数数组 inorder 和 postorder ，其中 inorder 是二叉树的中序遍历， postorder 是同一棵树的后序遍历，请你构造并返回这颗 二叉树 。

代码示例：

function buildTree(inorder: number[], postorder: number[]): TreeNode | null {
    if (postorder.length === 0) return null;
    const rootVal: number = postorder.pop()!;
    const rootValIndex: number = inorder.indexOf(rootVal);
    const rootNode: TreeNode = new TreeNode(rootVal);
    rootNode.left = buildTree(inorder.slice(0, rootValIndex), postorder.slice(0, rootValIndex));
    rootNode.right = buildTree(inorder.slice(rootValIndex + 1), postorder.slice(rootValIndex));
    return rootNode;
};