关于二叉树:你真的了解二叉树吗手撕算法篇

分割咱们 ： 有道技术团队助手 ：ydtech01 / 邮箱：ydtech@rd.netease.com

前言

本文属于系列文章《你真的理解二叉树吗》的第二局部——手撕算法篇。

如果你还没有看过第一局部《你真的理解二叉树吗（树形构造根底篇）》的话，强烈建议先看一下第一局部的内容，这样你在解题时会更加锦上添花。很多第一篇外面曾经讲过的内容，在这里将不再赘述。

一、二叉树根底刷题局部

1.1 LeetCode 144 二叉树的前序遍历

解题思路

如果你有看过我上一篇文章《你真的理解二叉树吗（树形构造根底篇）》的话，应该曾经晓得了，咱们树的遍历天生就适宜应用 递归实现。

此外，还讲了如何设计和实现一个递归函数，如果对着两点不太理解或没看过上一篇文章的同学，请先移步《你真的理解二叉树吗（树形构造根底篇）》补一下根底先，这里就不赘述了，间接讲思路吧：

首先，先设计一下咱们的递归函数

1. 函数意义：前序遍历以 root 为根节点的二叉树
2. 边界条件：root 为空时无需遍历，间接返回 root
3. 递归过程：别离前序遍历左子树和前序遍历右子树

代码演示

/*
 * @lc app=leetcode.cn id=144 lang=typescript
 *
 * [144] 二叉树的前序遍历
 */

// @lc code=start
/**
 * Definition for a binary tree node.
 * class TreeNode {
 *     val: number
 *     left: TreeNode | null
 *     right: TreeNode | null
 *     constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {*         this.val = (val===undefined ? 0 : val)
 *         this.left = (left===undefined ? null : left)
 *         this.right = (right===undefined ? null : right)
 *     }
 * }
 */

function preorderTraversal(root: TreeNode | null, arr: number[]=[]): number[] {
    // 判断边界条件
    if(root) {
        // 因为是前序遍历，所以先将根节点退出数组
        arr.push(root.val);
        // 递归遍历左子树和右子树
        preorderTraversal(root.left, arr);
        preorderTraversal(root.right, arr);
    }
    return arr;
};
// @lc code=end

以上是惯例的递归形式实现，咱们也能够应用 迭代的形式 实现：

/**
 * 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
 * @return {number[]}
 */
var preorderTraversal = function(root) {
      // 用一个栈辅助实现迭代遍历
    const stack = [];
      // 后果数组
    const res = [];
      // 以后节点
    let cur = root;
        // 如果以后节点为空或者栈为空时完结循环
    while(cur || stack.length>0) {while(cur) {
            // 因为是前序遍历，所以根节点先寄存到后果数组
            res.push(cur.val);
              // 为了在咱们走到左子树的底部时，可能回到根节点持续遍历右子树，因而，先将根节点存入栈中
            stack.push(cur);
              // 持续遍历左子树，直到遍历到叶子节点
            cur = cur.left;
        }
          // 左子树遍历完了，咱们须要遍历右子树了，首先咱们先要从栈顶把最近的一个根节点弹出
        cur = stack.pop();
          // 遍历弹出的这个根节点的右子树
        cur = cur.right;
    }
    return res;
};

1.2 LeetCode 589 N 叉树的前序遍历

解题思路

解题思路起始跟二叉树的解题思路截然不同，这里就不再赘述了。

首先，先设计一下咱们的递归函数

1. 函数意义：前序遍历以 root 为根节点的 N 叉树
2. 边界条件：root 为空时无需遍历，间接返回后果数组
3. 递归过程：别离 root 下端的所有子树进行递归遍历

代码演示

/*
 * @lc app=leetcode.cn id=589 lang=typescript
 *
 * [589] N 叉树的前序遍历
 */

// @lc code=start
/**
 * Definition for node.
 * class Node {
 *     val: number
 *     children: Node[]
 *     constructor(val?: number) {*         this.val = (val===undefined ? 0 : val)
 *         this.children = []
 *     }
 * }
 */

function preorder(root: Node | null, arr: number[] = []): number[] {
    // 边界条件
    if(!root) return arr;
    // 前序遍历，先将根节点放入后果数组
    arr.push(root.val);
    // 循环递归调用所有的子节点
    root.children.forEach(child => {preorder(child, arr);
    });
    return arr;
};
// @lc code=end

1.3 LeetCode 226 翻转二叉树

解题思路

咱们要反转一个二叉树，就要先将这个二叉树的左子树的子树和右子树的子树先反转，而后再反转根节点的左右子树。

这里利用到了 js 中的解构赋值的新个性进行高效疾速反转。

首先，先设计一下咱们的递归函数

1. 函数意义：反转以 root 为根节点的二叉树
2. 边界条件：root 为空时无需反转，间接返回 root
3. 递归过程：别离反转 root 的左子树和右子树

代码演示

/*
 * @lc app=leetcode.cn id=226 lang=typescript
 *
 * [226] 翻转二叉树
 */

// @lc code=start
/**
 * Definition for a binary tree node.
 * class TreeNode {
 *     val: number
 *     left: TreeNode | null
 *     right: TreeNode | null
 *     constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {*         this.val = (val===undefined ? 0 : val)
 *         this.left = (left===undefined ? null : left)
 *         this.right = (right===undefined ? null : right)
 *     }
 * }
 */

function invertTree(root: TreeNode | null): TreeNode | null {
    // 边界条件，当 root 为空时间接返回
    if(!root) return root;
    // 先替换 root 的左右子树，这里咱们利用 js 的解构赋值的新个性能够迅速的替换左右子树
    [root.left, root.right] = [root.right, root.left];
    // 别离递归左右子树
    invertTree(root.left)
    invertTree(root.right)
    return root;
};
// @lc code=end

1.4 LeetCode 剑指 Offer32. 从上到下打印二叉树Ⅱ

解题思路

这道题其实就是咱们二叉树的层序遍历，将每一层的节点顺次输入。这里能够应用一个技巧，减少一个变量 k 代表以后遍历到二叉树的第几层，默认为 0，即默认是二叉树的第一层。

首先，先设计一下咱们的递归函数

1. 函数意义：将 root 为根节点端的左子树和右子树增加到以后层 k 所在的数组中
2. 边界条件：root 为空时无需遍历，间接返回，间接返回后果数组
3. 递归过程：别离递归遍历 root 的左子树和右子树，别忘了层数须要加 1

代码演示

/**
 * Definition for a binary tree node.
 * class TreeNode {
 *     val: number
 *     left: TreeNode | null
 *     right: TreeNode | null
 *     constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {*         this.val = (val===undefined ? 0 : val)
 *         this.left = (left===undefined ? null : left)
 *         this.right = (right===undefined ? null : right)
 *     }
 * }
 */

function levelOrder(root: TreeNode | null,k=0, res: number[][] = []): number[][] {
    // 边界条件，当 root 不存在时，间接返回后果数组
    if(!root) return res;
    // 如果后果数组的长度为 k, 阐明咱们筹备遍历新的一层，但这层还没有数组来存放数据，所以要新建一个数组放到后果数组开端
    if(res.length===k) res.push([]);
    // 将根节点的值放到第 k 位的数组中
    res[k].push(root.val);
    // 递归遍历左子树、右子树
    levelOrder(root.left, k+1, res);
    levelOrder(root.right, k+1, res);
    return res;
};

咱们二叉树层序遍历的实现不仅能够应用递归，应用 队列 + 迭代 的形式也能够实现，思路也都差不多。

/**
 * Definition for a binary tree node.
 * class TreeNode {
 *     val: number
 *     left: TreeNode | null
 *     right: TreeNode | null
 *     constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {*         this.val = (val===undefined ? 0 : val)
 *         this.left = (left===undefined ? null : left)
 *         this.right = (right===undefined ? null : right)
 *     }
 * }
 */
function levelOrder(root: TreeNode | null, res: number[][]=[]): number[][] {
    // 边界条件，root 不存在是间接返回空数组
    if(!root) return res;
    // 用一个队列来存储节点，初始时根节点入队
    const queue: TreeNode[] = [root];
    // 用于记录以后遍历到了第几层
    let k = 0;
    while(queue.length!==0) {
        // 当层数与后果数组长度统一时，阐明遍历到了下一层，但没有一个数组用来寄存下一层的数据，因而在后果数组最初放一个空数组
        if(k===res.length) res.push([]);
        // 将队列中的所有节点顺次弹出，此时，队列中的所有节点都是以后层的节点，并且是从左到右排列的
        let queueLen = queue.length;
        // 留神，咱们这行的终止条件是针对于本次循环的队列长度，如果在循环过程中动静退出队列中的元素，是不会循环到的，因而，能够在循环过程中
        // 一直的将有子节点的元素的子节点压入队列而不必放心把下一层的数据也在本行输入
        while(queueLen--) {
            // 当根节点出队并将后果压入到第 k 层的数组中
            const item = queue.shift();
            res[k].push(item.val);
            // 如果左子树存在则左子树入队
            item.left && queue.push(item.left);
            // 右子树存在，则右子树入队
            item.right && queue.push(item.right);
        }
        // 本层所有节点解决完后，记得层数加一，筹备遍历下一层
        k++;
    }
    return res;
};

1.5 LeetCode 107 二叉树的层序遍历Ⅱ

解题思路

这道题起始跟上一道题没什么区别，仅仅是将上一道题的后果数组反转，这个在 js 中实现极其简略，就不再赘述了。

代码演示

/*
 * @lc app=leetcode.cn id=107 lang=typescript
 *
 * [107] 二叉树的层序遍历 II
 */

// @lc code=start
/**
 * Definition for a binary tree node.
 * class TreeNode {
 *     val: number
 *     left: TreeNode | null
 *     right: TreeNode | null
 *     constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {*         this.val = (val===undefined ? 0 : val)
 *         this.left = (left===undefined ? null : left)
 *         this.right = (right===undefined ? null : right)
 *     }
 * }
 */

function _lavelOrder(root: TreeNode|null, k: number, arr: number[][] = []): number[][] {if(!root) return arr;
    if(arr.length===k) arr.push([]);
    arr[k].push(root.val);
    _lavelOrder(root.left, k+1, arr);
    _lavelOrder(root.right, k+1, arr);
    return arr;
}

function levelOrderBottom(root: TreeNode | null): number[][] {const res = _lavelOrder(root, 0);
    // 应用双指针形式替换反转数组
    for(let i=0,j=res.length-1;i<j;i++,j--) {[res[i], res[j]] = [res[j], res[i]];
    }
    return res;
        // 也能够间接应用数组自带的反转办法
    // return res.reverse();};
// @lc code=end

1.6 LeetCode 103 二叉树的锯齿形层序遍历

解题思路

这一题其实是下面两题思路的综合，咱们只须要先依照失常的层序遍历输入失去后果数组，而后将后果数组中的奇数行进行翻转就能够了。

当然，咱们能够用更好的办法，就是在进行层序遍历时，直接判断以后的层数 k 是奇数还是偶数，如果是奇数就往数组后面增加元素，否则往数组前面增加元素，这样就不须要额定再反转数组了。

代码演示

计划一：先失常层序遍历，而后将奇数行数组反转

function _zigzagLevelOrder(root: TreeNode | null, k:number=0, res: number[][]=[]): number[][] {if(!root) return res;
    if(k===res.length) res.push([]);
    res[k].push(root.val);
    _zigzagLevelOrder(root.left, k + 1, res);
    _zigzagLevelOrder(root.right, k + 1, res);
    return res;
};

function zigzagLevelOrder(root: TreeNode | null): number[][] {const res = _zigzagLevelOrder(root);
    // 将奇数行反转
    return res.map((item, index) => {if(index&1) {item = item.reverse();
        }
        return item;
    })
}

计划二：在进行层序遍历时，如果 k 是奇数，则从数组后面开始增加元素，否则从前面增加元素

function _zigzagLevelOrder(root: TreeNode | null, k:number=0, res: number[][]=[]): number[][] {if(!root) return res;
    if(k===res.length) res.push([]);
    (k&1)?res[k].unshift(root.val):res[k].push(root.val);
    _zigzagLevelOrder(root.left, k + 1, res);
    _zigzagLevelOrder(root.right, k + 1, res);
    return res;
};

function zigzagLevelOrder(root: TreeNode | null): number[][] {return _zigzagLevelOrder(root);
}

二、二叉树进阶刷题局部

2.1 LeetCode 110 均衡二叉树

解题思路

概念：对于任意一个子树而言，他的左右子树的高度差的绝对值不超过 1 的树被称为均衡二叉树。

那么，按照题意，咱们能想到的就是计算一棵树的左右子树的树高，而后看看他们差绝对值是否大于 1，为了仅应用一次递归就判断出这棵树是否是均衡树，咱们能够在计算树高的时候，假如如果这棵树不是均衡树，也就是说左右子树树高差的绝对值是大于 1 的时候，咱们就间接返回一个正数，如 -1，这样，当咱们的程序执行完后，只有判断 树高是否小于 0 就能够晓得以后的树是否是均衡树了。

首先，先设计一下咱们的递归函数

1. 函数意义：在计算 root 为根节点的树的树高的同时，如果树不均衡，则返回一个正数
2. 边界条件：当 root 为空时，树高为 0
3. 递归过程：别离计算左右子树的树高，整个树的树高就是左右子树树高最大值加一

代码演示

/*
 * @lc app=leetcode.cn id=110 lang=typescript
 *
 * [110] 均衡二叉树
 */

// @lc code=start
/**
 * Definition for a binary tree node.
 * class TreeNode {
 *     val: number
 *     left: TreeNode | null
 *     right: TreeNode | null
 *     constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {*         this.val = (val===undefined ? 0 : val)
 *         this.left = (left===undefined ? null : left)
 *         this.right = (right===undefined ? null : right)
 *     }
 * }
 */
function getHeight(root: TreeNode | null): number {
    // 边界条件，如果根节点为空，则树高 0
    if(!root) return 0;
    // 别离计算左右子树的树高
    const lH = getHeight(root.left);
    const rH = getHeight(root.right);
    // 假如：如果以后 root 的左右子树不均衡，则返回一个正数，如 -1
      // 除此之外，因为是递归程序，如果左右子树的子树的高小于 0，那就阐明他们的子树曾经不均衡了，无需持续递归，间接返回 -1
    if(Math.abs(lH-rH)>1 || lH < 0 || rH < 0) return -1;
    // 一个树的树高，应该是左右子树的树高最大值加一
    return Math.max(lH, rH) + 1;

}
function isBalanced(root: TreeNode | null): boolean {
    // 只有树高大于等于 0，阐明这颗树是均衡的
    return getHeight(root) >= 0;
};
// @lc code=end

2.2 LeetCode 112 门路总和

解题思路

这道题的解题思路其实就是在咱们一直往下找的时候，都把 targetNum 与以后的节点的值计算出一个差值，作为下一次递归时的 targetNum，这样，当咱们找到叶子节点的时候，只有叶子节点端的值等于 targetNum 的话，就阐明存在这条门路了。

首先，先设计一下咱们的递归函数

1. 函数意义：在一个以 root 为根节点的二叉树中是否可能找到节点总和等于 targetNum 的值
2. 边界条件：当 root 为空时，不可能存在，返回 false, 此外，如果以后节点是叶子节点（没有左子树和右子树的节点），那么这个节点的值必须等于 targetNum
3. 递归过程：递归判断左子树和右子树是否满足条件，须要留神的是，咱们传入到递归函数中的 targetNum，须要与以后节点计算插值再传下去。

代码演示

/*
 * @lc app=leetcode.cn id=112 lang=typescript
 *
 * [112] 门路总和
 */

// @lc code=start
/**
 * Definition for a binary tree node.
 * class TreeNode {
 *     val: number
 *     left: TreeNode | null
 *     right: TreeNode | null
 *     constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {*         this.val = (val===undefined ? 0 : val)
 *         this.left = (left===undefined ? null : left)
 *         this.right = (right===undefined ? null : right)
 *     }
 * }
 */

function hasPathSum(root: TreeNode | null, targetSum: number): boolean {
    // 边界条件，如果 root 为空时，间接返回 false
    if(!root) return false;
    // 如果以后节点是叶子节点，那么这个节点的值必须等于 targetSum
    if(!root.left && !root.right) return root.val === targetSum;
    // 在左子树中查找是否有满足条件的门路
    if(root.left && hasPathSum(root.left, targetSum - root.val)) return true; 
    // 在右子树中查找是否有满足条件的门路
    if(root.right && hasPathSum(root.right, targetSum - root.val)) return true;
    // 都不满足则返回 false
    return false;
};
// @lc code=end

2.3 LeetCode 105 从前序与中序遍历序列结构二叉树

解题思路

如果有看过我写的上一篇文章《你真的理解二叉树吗（树形构造根底篇）》的同学应该是不会生疏了。上一篇文章中，曾经带着大家在思维逻辑层面上剖析过这题的解题思路了，然而没有一起编码实现，当初来还债了。

再来回顾一下大略的思路吧：

1. 先要找到根节点所在的地位
2. 递归建设左子树
3. 递归建设右子树
4. 而后把左右子树挂在根节点上

# 前序遍历输入后果
<1> 5 2 3 4
# 中序遍历输入后果
5 <1> 3 2 4
# 咱们晓得前序遍历的第一位就是咱们二叉树的根节点，那么，咱们依据这个根节点的数值在中序遍历中找到 1 所在的地位
# 这样，咱们就晓得，5 是左子树，3 2 4 是 1 的右子树序列，左子树无需持续解决，右子树能够间接递归解决失去最终的后果

代码演示

/*
 * @lc app=leetcode.cn id=105 lang=typescript
 *
 * [105] 从前序与中序遍历序列结构二叉树
 */

// @lc code=start
/**
 * Definition for a binary tree node.
 * class TreeNode {
 *     val: number
 *     left: TreeNode | null
 *     right: TreeNode | null
 *     constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {*         this.val = (val===undefined ? 0 : val)
 *         this.left = (left===undefined ? null : left)
 *         this.right = (right===undefined ? null : right)
 *     }
 * }
 */

function buildTree(preorder: number[], inorder: number[]): TreeNode | null {if(preorder.length===0) return null;
      // 用于记录根节点在中序遍历中的地位
    let pos = 0;
    // 找到根节点在中序遍历序列中的地位
    while(inorder[pos] !== preorder[0]) ++pos;
        // 别离用来存储拆分后的左右子树的前序和中序遍历序列
    let l_pre = [], l_in = [], r_pre=[],r_in=[];

    // 将左子树的前序遍历序列和中序遍历序列存起来
    for(let i=0;i<pos;i++) {l_pre.push(preorder[i+1]);
        l_in.push(inorder[i]);
    }
    // 将右子树的前序遍历和中序遍历的序列存起来
    for(let i=pos+1;i<preorder.length;i++) {r_pre.push(preorder[i]);
        r_in.push(inorder[i]);
    }
    // 构建二叉树
    const node = new TreeNode(preorder[0], buildTree(l_pre, l_in), buildTree(r_pre, r_in));
    return node;

};
// @lc code=end

2.4 LeetCode 222 齐全二叉树的节点个数

解题思路

这道题就是让咱们算一下一棵树有几个节点，咱们只有晓得这样的一个公式：总结点数量 = 左子树节点数量 + 右子树节点数量 + 根节点数量（1） 即可

代码演示

/*
 * @lc app=leetcode.cn id=222 lang=typescript
 *
 * [222] 齐全二叉树的节点个数
 */

// @lc code=start
/**
 * Definition for a binary tree node.
 * class TreeNode {
 *     val: number
 *     left: TreeNode | null
 *     right: TreeNode | null
 *     constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {*         this.val = (val===undefined ? 0 : val)
 *         this.left = (left===undefined ? null : left)
 *         this.right = (right===undefined ? null : right)
 *     }
 * }
 */

function countNodes(root: TreeNode | null): number {
    // 边界条件，如果 root 不存在，则返回 0
    if(!root) return 0;
    return countNodes(root.left) + countNodes(root.right) + 1;
};
// @lc code=end

2.5 LeetCode 剑指 Offer 54 二叉搜寻树的第 k 大的节点

解题思路

二叉搜寻树：右子树上所有的值都会大于根节点的值，左子树上的所有节点都会小于根节点的值。所以，二叉搜寻树的中序遍历输入肯定是一个有序数组。

因为这是一颗二叉搜寻树，那么左子树的树必定小于根节点，右子树必定大于根节点。
从这个个性咱们就能够得出：

1. 如果要找第 k 大的树，并且 k 小于或者等于右子树节点数量的话，那咱们能够间接到 右子树中 去查找，
2. 如果 k 等于右子树节点数量加 1，那么阐明咱们要找的数其实就是 根节点
3. 如果不是上述两种状况，那么，咱们就间接在左子树中查找，不过此时，因为咱们曾经排除了根节点和右子树了，就不再是找左子树第 k 大的节点了，咱们应该 减去根节点和右子树节点 的数量

代码演示

/**
 * Definition for a binary tree node.
 * class TreeNode {
 *     val: number
 *     left: TreeNode | null
 *     right: TreeNode | null
 *     constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {*         this.val = (val===undefined ? 0 : val)
 *         this.left = (left===undefined ? null : left)
 *         this.right = (right===undefined ? null : right)
 *     }
 * }
 */
// 计算节点数量
function getCount(root: TreeNode): number {if(!root) return 0;
    return getCount(root.left) + getCount(root.right) + 1;
}
// 因为这是一颗二叉搜寻树，那么左子树的树必定小于根节点，右子树必定大于根节点
// 从这个个性咱们就能够得出：// 如果要找第 k 大的树，并且 k 小于或者等于右子树节点数量的话，那咱们能够先到右子树中去查找，// 如果 k 等于右子树节点数量加 1，那么阐明咱们要找的数其实就是根节点
// 如果不是上述两种状况，那么，咱们就间接在左子树中查找，不过此时，因为咱们曾经排除了根节点和右子树了，就不再是找左子树第 k 大的节点了，咱们应该减去根节点和右子树节点的数量
function kthLargest(root: TreeNode | null, k: number): number {
    // 获取右子树节点数量
    const count_r = getCount(root.right);
    // 如果 k 小于等于右子树节点数量，则在右子树上查找第 k 大的树
    if(k<=count_r) return kthLargest(root.right, k);
    // 如果 k 等于右子树节点数量加 1，阐明要找的树就是根节点
    if(k===count_r+1) return root.val;
    // 否则去左子树查找第 k -(count_r+1)=k- count_r - 1 大的数
    return kthLargest(root.left, k - count_r - 1);
};

2.6 LeetCode 剑指 Offer 26 树的子结构

解题思路

这道题咱们其实就是在边界条件解决好之后，看一下 B 是否匹配一整颗 A 树，如果不能匹配，那么就看你一下 B 能不能匹配 A 的左子树或者其右子树，如果可能匹配上任意一个，就阐明 B 是 A 的子结构。

代码演示

/**
 * Definition for a binary tree node.
 * class TreeNode {
 *     val: number
 *     left: TreeNode | null
 *     right: TreeNode | null
 *     constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {*         this.val = (val===undefined ? 0 : val)
 *         this.left = (left===undefined ? null : left)
 *         this.right = (right===undefined ? null : right)
 *     }
 * }
 */
// 递归匹配子树结构
function isMatch(a: TreeNode, b: TreeNode) {
    // 如果 b 为空，必定匹配，返回 true
    if(!b) return true;
    // 如果 a 为空则不可能匹配，返回 false
    if(!a) return false;
    // 如果 a 和 b 的值不统一，返回 false
    if(a.val !== b.val) return false;
    // 别离递归匹配 a、b 的左子树和右子树
    return isMatch(a.left, b.left) && isMatch(a.right, b.right);
}

function isSubStructure(A: TreeNode | null, B: TreeNode | null): boolean {
    // 根据题意，如果 B 为空，则不是任何树的子结构，间接返回 false
    if(!B) return false;
    // 若 A 为空，B 不为空，则不可能匹配上，返回 false
    if(!A) return false;
    // 递归判断 A、B 是否可能匹配，如果匹配上了，则返回 true
    if(isMatch(A, B)) return true;
    // 下面的状况都不是，那么就别离去 A 的左子树和右子树看一下是否匹配，只有二者有一个匹配就算匹配胜利
    return isSubStructure(A.left, B) || isSubStructure(A.right, B);
};

2.7 LeetCode 622 二叉树的最大宽度

解题思路

这道题在实现上的确是有肯定的难度，咱们能够借助上一篇文章《你真的理解二叉树吗（树形构造根底篇）》中讲过的齐全二叉树的编号形式以及一个队列来辅助咱们实现这个题目。在齐全二叉树的编号中，如果以后节点的编号为 i，那么他的左子树的编号为 2 i，右子树的编号为 2 i+1，不过这题中，有可能会因为编号过大导致整形数据溢出的状况，所以咱们须要非凡解决。具体的解题思路，代码正文写得很分明，间接看代码吧。

代码演示

/*
 * @lc app=leetcode.cn id=662 lang=typescript
 *
 * [662] 二叉树最大宽度
 */

// @lc code=start
/**
 * Definition for a binary tree node.
 * class TreeNode {
 *     val: number
 *     left: TreeNode | null
 *     right: TreeNode | null
 *     constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {*         this.val = (val===undefined ? 0 : val)
 *         this.left = (left===undefined ? null : left)
 *         this.right = (right===undefined ? null : right)
 *     }
 * }
 */

// 为了不便存储节点和它对应编号，定义一个包装类
class Wrapper {constructor(public node: TreeNode, public idx: number){}}

function widthOfBinaryTree(root: TreeNode | null): number {
    // 用来存储后果
    let res = 0;
    // 定义一个包装类的队列，这个包装类能够存储节点和他对应的编号
    const queue: Wrapper[] = [];
    // 先将根节点和他的编号 0 退出队列
    queue.push(new Wrapper(root, 0));

    // 用于存储每一层有多少个节点
    let rowSize;
    while(rowSize = queue.length) {
        // 设置以后层最小编号和最大编号的初始值都为父节点的编号
        let lIdx = queue[0].idx, rIdx = queue[0].idx;

        // 遍历以后层的每一个元素
        while(rowSize--) {
            // 先将队首元素出队
            const {node, idx} = queue.shift();
            // 以后层最大编号为父节点的编号
            rIdx = idx;
            // 当存在左子树时，应用左子树根节点和其对应的编号创立包装类，并退出到队列
            // 其实这里，最难的就是这个编号如何界定。// 咱们有学过齐全二叉树的编号形式，能够参考这种编号形式，// 第 i 个节点的做子树根节点的编号为 2 *i, 右子树的编号为 2 *i+1
            // 所以，到了这里，咱们就间接应用 idx * 2 和 idx * 2 + 1 代表左子树和右子树编号
            // 如果咱们这么提交的话，会遇到一个问题，就是当咱们的树的节点足够大时，这个编号会超出
            // 咱们整数的范畴，那么，咱们要怎么在不影响程序运行后果的前提下，缩减这个编号，防止整数溢出呢
            // 咱们来想想，对于一个编号来说，其实最小和最大编号别离为 6 和 7，其实跟为 0 和 1 是没有实质上的区别的
            // 因为咱们拿这个编号并没有本质的作用，只是为了用这个编号计算差值，7- 6 的差值跟 1 - 0 的差值是一样的
            // 所以，咱们这边间接让以后的编号鉴于父节点的最小编号 lIdx，以此来缩减编号大小
            node.left && queue.push(new Wrapper(node.left, (idx - lIdx) * 2));
            node.right && queue.push(new Wrapper(node.right, (idx - lIdx) * 2 + 1));
        }
        // 一层循环完结后，咱们只有计算上一个宽度，与以后层最大编号减去最小编号加 1，而后两者取最大值找到最大宽即可
        // 例如：以后层最小和最大的编号是：0 和 8, 那么这一层其实有 8 -0+1= 9 个节点空间，也就是宽度为 9.
        res = Math.max(res, rIdx - lIdx + 1);
    }
    return res;
};
// @lc code=end