前端算法：树（力扣144、94、145、100、104题）
目录
一、树（Tree）
1.介绍
2.特点
3.基本术语
4.种类
二、树之操作
1.遍历
前序遍历（Pre-order Traversal）：访问根节点 -> 遍历左子树 -> 遍历右子树。
中序遍历（In-order Traversal）：遍历左子树 -> 访问根节点 -> 遍历右子树（用于 BST 时可得到排序结果）。
后序遍历（Post-order Traversal）：遍历左子树 -> 遍历右子树 -> 访问根节点。
层序遍历（Level-order Traversal）：逐层访问树的节点，通常使用队列实现。
2.插入和删除
3.查找
三、树的力扣算法实战
1.144. 二叉树的前序遍历
2.94. 二叉树的中序遍历
3.145. 二叉树的后序遍历
4.100. 相同的树
5.104. 二叉树的最大深度
一、树（Tree）
1.介绍
树（Tree）是一种重要的数据结构，广泛应用于计算机科学中。它由节点组成，并且有一个根节点，其他节点通过边连接形成层级关系。
2.特点
- 层级关系：树结构是分层的，根节点位于顶层，每个节点可以有多个子节点。
- 无环性：树中不存在环，即从一个节点出发不可能回到该节点。
- 节点的子节点：每个节点可以有零个或多个子节点。
3.基本术语
- 根节点：树的顶层节点。
- 叶子节点：没有子节点的节点。
- 子节点：某个节点直接连接的下层节点。
- 兄弟节点：同一父节点的子节点。
- 高度：树的高度是从根节点到最深叶子节点的最长路径的边数。
4.种类
-
树（Tree）：一般的树结构，没有特定的限制。
-
二叉树（Binary Tree）：每个节点最多有两个子节点。
- 完全二叉树（Complete Binary Tree）：除了最后一层外，其他层的节点都填满，最后一层的节点尽量向左排列。
- 满二叉树（Full Binary Tree）：每个节点要么是叶子节点，要么有两个子节点。
- 非完全二叉树（Incomplete Binary Tree）：不是完全二叉树的任意形式。
-
二叉搜索树（Binary Search Tree, BST）：一种特殊的二叉树，左子树的所有节点值小于根节点，右子树的所有节点值大于根节点。
-
自平衡树（Self-balancing Tree）：如 AVL 树和红黑树，保持树的高度平衡以优化查找效率。
-
N 叉树（N-ary Tree）：每个节点可以有 N 个子节点的树结构。
-
Trie（前缀树）：一种用于存储字符串的树，常用于快速查找和前缀匹配。
二、树之操作
1.遍历
前序遍历（Pre-order Traversal）：访问根节点 -> 遍历左子树 -> 遍历右子树。
// 前序遍历preOrderTraversal(node) {if (node) {console.log(node.value);this.preOrderTraversal(node.left);this.preOrderTraversal(node.right);}}中序遍历（In-order Traversal）：遍历左子树 -> 访问根节点 -> 遍历右子树（用于 BST 时可得到排序结果）。
// 中序遍历inOrderTraversal(node) {if (node) {this.inOrderTraversal(node.left);console.log(node.value);this.inOrderTraversal(node.right);}}后序遍历（Post-order Traversal）：遍历左子树 -> 遍历右子树 -> 访问根节点。
// 后序遍历postOrderTraversal(node) {if (node) {this.postOrderTraversal(node.left);this.postOrderTraversal(node.right);console.log(node.value);}}
层序遍历（Level-order Traversal）：逐层访问树的节点，通常使用队列实现。
// 层序遍历levelOrderTraversal() {if (!this.root) return;const queue = [this.root];while (queue.length > 0) {const node = queue.shift();console.log(node.value);if (node.left) queue.push(node.left);if (node.right) queue.push(node.right);}}2.插入和删除
插入：在二叉搜索树中，插入新节点时需要找到合适的位置，保证 BST 的性质。
// 插入insert(value) {const newNode = new TreeNode(value);if (this.root === null) {this.root = newNode;return;}this.insertNode(this.root, newNode);}insertNode(node, newNode) {if (newNode.value < node.value) {if (node.left === null) {node.left = newNode;} else {this.insertNode(node.left, newNode);}} else {if (node.right === null) {node.right = newNode;} else {this.insertNode(node.right, newNode);}}}删除：删除节点时可能需要重新调整树结构，以保持树的性质，尤其在 BST 中。
// 删除delete(value) {this.root = this.deleteNode(this.root, value);}deleteNode(node, value) {if (node === null) {return null;}if (value < node.value) {node.left = this.deleteNode(node.left, value);} else if (value > node.value) {node.right = this.deleteNode(node.right, value);} else {// 找到要删除的节点if (node.left === null && node.right === null) {return null; // 无子节点}if (node.left === null) {return node.right; // 只有右子节点}if (node.right === null) {return node.left; // 只有左子节点}// 找到右子树中的最小节点const minNode = this.findMinNode(node.right);node.value = minNode.value; // 替换值node.right = this.deleteNode(node.right, minNode.value); // 删除最小节点}return node;}3.查找
在树中查找节点的过程依赖于树的性质。对于二叉搜索树，可以通过比较节点值快速找到目标节点。
search(value) {return this.searchNode(this.root, value);}searchNode(node, value) {if (node === null) {return false;}if (value === node.value) {return true;}return value < node.value? this.searchNode(node.left, value): this.searchNode(node.right, value);}三、树的力扣算法实战
1.144. 二叉树的前序遍历
题目描述：给你二叉树的根节点 root ，返回它节点值的 前序 遍历。
示例 1：
输入：root = [1,null,2,3]
输出：[1,2,3]
示例 2：
输入：root = [1,2,3,4,5,null,8,null,null,6,7,9]
输出：[1,2,4,5,6,7,3,8,9]
示例 3：
输入：root = []
输出：[]
示例 4：
输入：root = [1]
输出：[1]
解题思路：将二叉树进行先序遍历（中左右：根节点->左子树->右子树）
代码：
var preorderTraversal = function(root) {const arr = []const fun = (node) =>{if(node){arr.push(node.val)fun(node.left)fun(node.right)}}fun(root)return arr
};2.94. 二叉树的中序遍历
题目描述：给定一个二叉树的根节点 root ，返回 它的 中序 遍历 。
示例 1：
输入：root = [1,null,2,3] 输出：[1,3,2]示例 2：
输入：root = [] 输出：[]示例 3：
输入：root = [1] 输出：[1]
解题思路：将二叉树进行中序遍历（左中右：左子树->根节点->右子树）
代码：
var inorderTraversal = function(root) {const arr = []const fun = (root) =>{if(!root) returnfun(root.left)arr.push(root.val)fun(root.right)}fun(root)return arr
};3.145. 二叉树的后序遍历
题目描述：给你一棵二叉树的根节点 root ，返回其节点值的 后序遍历 。
示例 1：
输入：root = [1,null,2,3]
输出：[3,2,1]
示例 2：
输入：root = [1,2,3,4,5,null,8,null,null,6,7,9]
输出：[4,6,7,5,2,9,8,3,1]
示例 3：
输入：root = []
输出：[]
示例 4：
输入：root = [1]
输出：[1]
解题思路：将二叉树进行中序遍历（左右中：左子树->右子树->根节点）
代码：
var postorderTraversal = function(root) {const arr = []const fun = (root) =>{if(!root) returnfun(root.left)fun(root.right)arr.push(root.val)}fun(root)return arr
};4.100. 相同的树
题目描述：
给你两棵二叉树的根节点 p 和 q ，编写一个函数来检验这两棵树是否相同。
如果两个树在结构上相同，并且节点具有相同的值，则认为它们是相同的。
示例 1：
输入：p = [1,2,3], q = [1,2,3] 输出：true示例 2：
输入：p = [1,2], q = [1,null,2] 输出：false示例 3：
输入：p = [1,2,1], q = [1,1,2] 输出：false
解题思路：首先判断两个节点是否都为空，是则返回true;如果一个为空一个不为空，则返回false，再判断两个节点的val值是否相同，不同返回false，依次进行传入两棵树的左节点和右节点
代码：
var isSameTree = function(p, q) {if(p === null && q === null) return true;if(p === null || q === null) return falseif(p.val !== q.val) return falsereturn isSameTree(p.left,q.left) && isSameTree(p.right,q.right)
};5.104. 二叉树的最大深度
题目描述：
给定一个二叉树 root ，返回其最大深度。
二叉树的 最大深度 是指从根节点到最远叶子节点的最长路径上的节点数。
示例 1：
输入：root = [3,9,20,null,null,15,7] 输出：3示例 2：
输入：root = [1,null,2] 输出：2
解题思路： 首先判断树是否为空，空则返回0，将树放入栈中，以栈的长度为值进行遍历，将栈的长度定义一个值len，每循环一次计数器num+1，len--，依次弹出stack的栈中元素，判断是否有左右子节点，在将其压入栈中，最后返回num值
代码
var maxDepth = function(root) {if(!root) return 0const stack = [root]let num = 0while(stack.length){let len = stack.lengthnum++while(len--){const o = stack.shift()o.left && stack.push(o.left)o.right && stack.push(o.right)}}return num
};