- 深度优先遍历：尽可能深的搜索树的分支
- 广度优先遍历：先访问离根节点最近的节点
1.深度优先遍历
- 访问根节点
对跟节点的children挨个进行深度优先遍历
const dfs = (root) => {console.log(root.val)root.children.forEach(dfs)}
2.广度优先遍历
新建一个队列，把根节点入队
- 把队头出队并访问
- 把队头的children挨个入队
重复二三步，直到队列为空
const bfs = (root) => {// 对头入队const q = [root]// 循环条件 - 队列不为空while(q.length > 0) {// 拿到队头const nq = q.shift()console.log(nq.val)// 队头的children里面的child挨个入队nq.children.forEach(child => {q.push(child)})}}
3.二叉树的先中后序遍历（递归）
树中每个节点最多能有两个子节点
- 在JS中常用Object模拟二叉树
```javascript
const bt = {
val: 1,
left: {
}, right: {val: 2,left: {val: 4,left: null,right: null,},right: {val: 5,left: null,right: null,},
}, };val: 3,left: {val: 6,left: null,right: null,},right: {val: 7,left: null,right: null,},
module.exports = bt;
<a name="BQFEI"></a>## 先序遍历- 访问根节点- 对根节点的左子树进行先序遍历- 对根节点的右子树进行先序遍历```javascriptconst preorder = (root) => {if (!root) { return; }console.log(root.val);preorder(root.left);preorder(root.right);};
中序遍历
- 对根节点的左子树进行中序遍历
- 访问根节点
- 对根节点的右子树进行中序遍历
const inorder = (root) => {
if (!root) { return; }
inorder(root.left);
console.log(root.val);
inorder(root.right);
};
后序遍历
- 对根节点的左子树进行后序遍历
- 对根节点的右子树进行后序遍历
- 访问根节点
const postorder = (root) => {
if (!root) { return; }
postorder(root.left);
postorder(root.right);
console.log(root.val);
};
4.二叉树的先中后序遍历（非递归）
先序遍历
const preorder = (root) => {
if(!root) return;
// 利用数据结构栈来遍历
const stack = [root];
while (stack.length) {
// 1.先访问根节点
const n = stack.pop();
console.log(n.val);
// 3.访问右节点
if(n.right) stack.push(n.right);
// 2.访问左节点
if(n.left) stack.push(n.left)
}
}
中序遍历
const inorder = (root) => {
if(!root) return;
// 利用数据结构栈来遍历
const stack = [root];
// 利用指针
let p = root
while (stack.length) {
while(p) {
// 1.先访问左节点
stack.push(p)
p = p.left
}
// 2.再访问根节点
const n = stack.pop();
console.log(n.val);
// 3.再访问右节点
p = p.right
}
}
后序遍历
- 倒置后序遍历为一个先序遍历
- 利用栈后进先出的特性，将先序遍历的结果倒着输出
const postorder = (root) => { if (!root) return const stack = [root]; const outputStack = []; while (stack.length) { const n = stack.pop(); // 1.根 outputStack.push(n) // 3.左 if (n.left) stack.push(n.left); // 2.右 if (n.right) stack.push(n.right); } while (outputStack.length){ // 左，右，根 const n = outputStack.pop(); console.log(n.val) } }5.前端与树：遍历JSON的所有节点值
```javascript const json = { a: { b: { c: 1 } }, d: [1, 2], };
const dfs = (n, path) => { console.log(n, path); Object.keys(n).forEach(k => { dfs(n[k], path.concat(k)); }); };
dfs(json, []);
<a name="Xgaq1"></a>
# 题目
<a name="gXEIi"></a>
## 1.二叉树的最大深度-104
给定一个二叉树，找出其最大深度。
二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。
说明: 叶子节点是指没有子节点的节点。
示例：<br />给定二叉树 [3,9,20,null,null,15,7]，
3<br /> / \<br /> 9 20<br /> / \<br /> 15 7<br />返回它的最大深度 3 。
思路：
- 求最大深度，考虑使用深度优先遍历
- 在深度优先遍历过程中，记录每个节点所在的层级，找出最大层级即可
解题步骤：
- 新建变量，记录最大深度
- 深度优先遍历整棵树，并记录每个节点的层级，同时不断刷新最大深度这个变量
```javascript
/**
* 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 maxDepth = function(root) {
// 初始化返回结果
let res = 0
const dfs = (n, l) => {
if(!n) return
// 只有在叶子节点的时候才计算
if(!n.left && !n.right) res = Math.max(res, l)
// 先遍历左节点
dfs(n.left, l + 1)
// 再遍历右节点
dfs(n.right, l + 1)
}
dfs(root, 1)
return res
};
2.二叉树的最小深度-111
给定一个二叉树，找出其最小深度。
最小深度是从根节点到最近叶子节点的最短路径上的节点数量。
说明：叶子节点是指没有子节点的节点。
示例 1：
输入：root = [3,9,20,null,null,15,7]
输出：2
示例 2：
输入：root = [2,null,3,null,4,null,5,null,6]
输出：5
提示：
- 树中节点数的范围在 [0, 105] 内
- -1000 <= Node.val <= 1000
思路：
- 求最小深度遍历，考虑使用广度优先遍历
- 在广度优先遍历过程中，遇到叶子结点，停止遍历，返回节点层级
解题步骤：
- 广度优先遍历，并记录每个节点的层级
- 广度优先遍历，直到遇到叶子结点，刷新该该变量，停止遍历
```javascript
/**
- 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 minDepth = function(root) {
// 空树，返回0
if(!root) return 0
// 定义栈，数组中嵌套一个数组，第一个表示节点，第二个表示层级
const q = [[root, 1]]
// 循环条件 - 当栈中还有值
while(q.length){
}// 拿到根节点的值 const [n, l] = q.shift() // 如果是叶子节点，停止循环，返回当前层级 if(!n.left && !n.right) { return l } // 将左右节点入栈，层级加1 if(n.left) q.push([n.left, l + 1]) if(n.right) q.push([n.right, l + 1])
};
<a name="entV9"></a>
## 3.二叉树的层序遍历-102
给你一个二叉树，请你返回其按 **层序遍历** 得到的节点值。 （即逐层地，从左到右访问所有节点）。
示例：<br />二叉树：[3,9,20,null,null,15,7],
3<br /> / \<br /> 9 20<br /> / \<br /> 15 7<br />返回其层序遍历结果：
[<br /> [3],<br /> [9,20],<br /> [15,7]<br />]
思路：
- 层序遍历就是广度优先遍历
- 在遍历的时候需要记录当前节点所在的层级，方便将其添加到不同的数组中
解题步骤：
- 广度优先遍历二叉树
- 遍历的过程中，记录每个节点的层级，并将其添加到不同的数组中
```javascript
/**
* 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 levelOrder = function(root) {
if(!root) return []
// 定义队列，记录元素和层级
let q = [[root, 0]]
const res = []
while(q.length) {
// 广度遍历
// 拿到根节点
const [n, l] = q.shift()
// 同一层级没有值，则追加一个数组
if(!res[l]) {
res.push([n.val])
} else {
// 如果在同一层级并且有值时，直接追加
res[l].push(n.val)
}
// 遍历左节点的同时，层级加1
if(n.left) q.push([n.left, l + 1])
if(n.right) q.push([n.right, l + 1])
}
return res
};
/**
* 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 levelOrder = function(root) {
if(!root) return []
// 定义队列
let q = [root]
const res = []
while(q.length) {
// 拿到当前队列的长度
let len = q.length
// 每次循环给res的末尾追加一个空数组
res.push([])
// 当len为1 时，就是根节点，只执行一次
// 大于1时就是其子节点，循环len次，就可以拿到所有子节点
while(len--) {
// 根节点出队
const n = q.shift()
// 将同层级的空数组追加所有同级节点
res[res.length - 1].push(n.val)
if(n.left) q.push(n.left)
if(n.right) q.push(n.right)
}
}
return res
};
4.二叉树的中序遍历-94
给定一个二叉树的根节点 root ，返回它的 中序 遍历。
示例 1：
输入：root = [1,null,2,3]
输出：[1,3,2]
示例 2：
输入：root = []
输出：[]
示例 3：
输入：root = [1]
输出：[1]
示例 4：
输入：root = [1,2]
输出：[2,1]
示例 5：
输入：root = [1,null,2]
输出：[1,2]
提示：
- 树中节点数目在范围 [0, 100] 内
- -100 <= Node.val <= 100
/** * 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 inorderTraversal = function(root) { const res = [] // 中序遍历 左根右 const inorder = (n) => { if(!n) return[] if(n.left) inorder(n.left) res.push(n.val) if(n.right) inorder(n.right) } inorder(root) return res };/** * 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 inorderTraversal = function(root) { let res = [] if(!root) return[] let stack = [] let p = root while(stack.length || p) { // 先访问左节点 while(p) { stack.push(p) p = p.left } const n = stack.pop() res.push(n.val) p = n.right } return res };5.路径总和-112
给你二叉树的根节点 root 和一个表示目标和的整数 targetSum ，判断该树中是否存在 根节点到叶子节点 的路径，这条路径上所有节点值相加等于目标和 targetSum 。
叶子节点 是指没有子节点的节点。
示例 1：
输入：root = [5,4,8,11,null,13,4,7,2,null,null,null,1], targetSum = 22
输出：true
示例 2：
输入：root = [1,2,3], targetSum = 5
输出：false
示例 3：
输入：root = [1,2], targetSum = 0
输出：false
提示：
- 树中节点的数目在范围 [0, 5000] 内
- -1000 <= Node.val <= 1000
- -1000 <= targetSum <= 1000
思路：
- 在深度优先遍历的过程中，记录当前路径的节点值的和
- 在叶子节点处，判断当前路径的节点值的和是否等于目标值
解题步骤：
- 在深度优先遍历的过程中，记录当前路径的节点值的和，在叶子节点处，判断当前路径的节点值的和是否等于目标值
- 遍历结束，如果没有匹配，就返回false
```javascript
/**
- 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
- @param {number} targetSum
- @return {boolean}
*/
var hasPathSum = function(root, targetSum) {
if(!root) return false
let res = false
// 深度优先遍历
const dfs = (n, v) => {
} dfs(root, root.val) return res// 如果是叶子节点，就判断当前路径的和是否匹配 if(!n.left && !n.right && v === targetSum ) { res = true } // 深度遍历 if(n.left) dfs(n.left, v + n.left.val) if(n.right) dfs(n.right, v + n.right.val)
}; ```
若有收获，就点个赞吧
0 人点赞
