目录

二叉树

题目

判断是不是平衡二叉树

题链接

解析

核心思想

答案

二叉树的中序遍历

原题链接

解析

核心思想

答案

二叉树最大深度、对称二叉树、合并二叉树

二叉树

该类题目的解决一般是通过节点的遍历去实现，一般是分两种。

一是递归（深度优先），该方法通常代码比较简单，难懂。首先需要确定入参和返回的内容，然后确定层级之间的关系，最后去找递归的出口。

二是广度优先（该方法一般只有可以分层次处理的才能用），该方法代码量多，易懂。首先借助数组存储第一层的节点，然后每次将数组中的节点分批从数组头部取出（当对比2个节点时就一次取2个），处理完后将对应的子节点分批再从数组尾部存入数组（注意需要对比的子节点相邻存入，这样取出正好配对）。递归上述步骤直到数组为空。

题目

判断是不是平衡二叉树

输入一棵节点数为 n 二叉树，判断该二叉树是否是平衡二叉树。

在这里，我们只需要考虑其平衡性，不需要考虑其是不是排序二叉树

平衡二叉树（Balanced Binary Tree），具有以下性质：它是一棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。

样例解释：

样例二叉树如图，为一颗平衡二叉树

注：我们约定空树是平衡二叉树。

function TreeNode(x) {this.val = x;this.left = null;this.right = null;
}
function IsBalanced_Solution(pRoot) {}

题链接

判断是不是平衡二叉树_牛客题霸_牛客网

解析

注意该题无法使用广度优先算法，因为无法分层次处理（通过层次是无法判断是否为平衡数，可能出现底部相邻叶子节点高度只差1，而顶部的左右子树高度相差超过1）。

核心思想

递归、深度优先：

1.确定入参1个，出参，由于是要判断相邻子节点深度，所以出参返回深度差小于1&&深度，即小于1时返回该节点的深度，最后将深度数值通过boolean转换。

2.找到上下层的关系，f(x)=Math.abs(f(x.left)-f(x.right))<=1 && Math(x.left,x.right)+1

3.找出口，这里注意当f(x.left)和f(x.right)返回为false时要直接return false。

答案

function IsBalanced_Solution(pRoot) {function check(pRoot) {if (!pRoot) return 1let left = check(pRoot.left)if (!left) return falselet right = check(pRoot.right)if (!right) return falsereturn Math.abs(right - left) <= 1 && Math.max(left, right) + 1}return Boolean(check(pRoot))
}

二叉树的中序遍历

给定一个二叉树的根节点root，返回它的中序遍历（左根右）结果。

例如下图返回顺序为0、1、3、4、5、7、11、12、14

原题链接

二叉树的中序遍历_牛客题霸_牛客网 

解析

注意该题无法使用广度优先算法，因为无法分层次处理。

核心思想

递归：

1.确定入参和出参，由于返回的是一个数组为遍历的节点值。所以新借助函数将值在遍历过程中存储到数组中，该函数入参1个，返回为空。

2.确定上下层关系，f(x)为将x加入数组中，则当x存在时，应该先满足加入左节点，再加入中间节点，后加入右节点。f(x)= f(x.left)  + 加入x节点 + f(x.right)。

3.找出口，x不存在时不执行任何操作

方法二（借助数组循环）：

1.首先将所有的左节点和根节点加入stack数组中。

2.读取第一个左节点（最左端节点），值存入res数组。如果该节点右节点不存在，则读取下一个左节点重复2操作，如果存在则将右节点上的所有左节点加入stack数组中，重复2操作。

3.当stack为空时返回res数组。

答案

方法一（递归）

function inorderTraversal(root) {let arr = []function order(root) {if (root) {order(root.left)arr.push(root.val)order(root.right)}}order(root)return arr
}

方法二

function inorderTraversal( root ) {const res = []if(!root) return res;function inOrder(root,res){let node = rootconst stack = []while(stack.length||node){while(node){stack.push(node)node = node.left}const top = stack.pop()res.push(top.val)node = top.right}}inOrder(root, res)return res
}

二叉树最大深度、对称二叉树、合并二叉树

算法题--广度优先算法（素数行李箱密码、二叉树的最大深度、对称二叉树、合并二叉树解法加步骤）_行李箱密码计算_YF-SOD的博客-CSDN博客