網(wǎng)站建設(shè)平臺(tái)合同模板下載優(yōu)化器
目錄
一、樹(shù)（Tree）
1.介紹
2.特點(diǎn)
3.基本術(shù)語(yǔ)
4.種類
二、樹(shù)之操作
1.遍歷
前序遍歷（Pre-order Traversal）：訪問(wèn)根節(jié)點(diǎn) -> 遍歷左子樹(shù) -> 遍歷右子樹(shù)。
中序遍歷（In-order Traversal）：遍歷左子樹(shù) -> 訪問(wèn)根節(jié)點(diǎn) -> 遍歷右子樹(shù)（用于 BST 時(shí)可得到排序結(jié)果）。
后序遍歷（Post-order Traversal）：遍歷左子樹(shù) -> 遍歷右子樹(shù) -> 訪問(wèn)根節(jié)點(diǎn)。
層序遍歷（Level-order Traversal）：逐層訪問(wèn)樹(shù)的節(jié)點(diǎn)，通常使用隊(duì)列實(shí)現(xiàn)。
2.插入和刪除
3.查找
三、樹(shù)的力扣算法實(shí)戰(zhàn)
1.144. 二叉樹(shù)的前序遍歷
2.94. 二叉樹(shù)的中序遍歷
?3.145. 二叉樹(shù)的后序遍歷
4.100. 相同的樹(shù)
5.104. 二叉樹(shù)的最大深度
一、樹(shù)（Tree）
1.介紹
樹(shù)（Tree）是一種重要的數(shù)據(jù)結(jié)構(gòu)，廣泛應(yīng)用于計(jì)算機(jī)科學(xué)中。它由節(jié)點(diǎn)組成，并且有一個(gè)根節(jié)點(diǎn)，其他節(jié)點(diǎn)通過(guò)邊連接形成層級(jí)關(guān)系。
2.特點(diǎn)
- 層級(jí)關(guān)系：樹(shù)結(jié)構(gòu)是分層的，根節(jié)點(diǎn)位于頂層，每個(gè)節(jié)點(diǎn)可以有多個(gè)子節(jié)點(diǎn)。
- 無(wú)環(huán)性：樹(shù)中不存在環(huán)，即從一個(gè)節(jié)點(diǎn)出發(fā)不可能回到該節(jié)點(diǎn)。
- 節(jié)點(diǎn)的子節(jié)點(diǎn)：每個(gè)節(jié)點(diǎn)可以有零個(gè)或多個(gè)子節(jié)點(diǎn)。
3.基本術(shù)語(yǔ)
- 根節(jié)點(diǎn)：樹(shù)的頂層節(jié)點(diǎn)。
- 葉子節(jié)點(diǎn)：沒(méi)有子節(jié)點(diǎn)的節(jié)點(diǎn)。
- 子節(jié)點(diǎn)：某個(gè)節(jié)點(diǎn)直接連接的下層節(jié)點(diǎn)。
- 兄弟節(jié)點(diǎn)：同一父節(jié)點(diǎn)的子節(jié)點(diǎn)。
- 高度：樹(shù)的高度是從根節(jié)點(diǎn)到最深葉子節(jié)點(diǎn)的最長(zhǎng)路徑的邊數(shù)。
4.種類
-
樹(shù)（Tree）：一般的樹(shù)結(jié)構(gòu)，沒(méi)有特定的限制。
-
二叉樹(shù)（Binary Tree）：每個(gè)節(jié)點(diǎn)最多有兩個(gè)子節(jié)點(diǎn)。
- 完全二叉樹(shù)（Complete Binary Tree）：除了最后一層外，其他層的節(jié)點(diǎn)都填滿，最后一層的節(jié)點(diǎn)盡量向左排列。
- 滿二叉樹(shù)（Full Binary Tree）：每個(gè)節(jié)點(diǎn)要么是葉子節(jié)點(diǎn)，要么有兩個(gè)子節(jié)點(diǎn)。
- 非完全二叉樹(shù)（Incomplete Binary Tree）：不是完全二叉樹(shù)的任意形式。
-
二叉搜索樹(shù)（Binary Search Tree, BST）：一種特殊的二叉樹(shù)，左子樹(shù)的所有節(jié)點(diǎn)值小于根節(jié)點(diǎn)，右子樹(shù)的所有節(jié)點(diǎn)值大于根節(jié)點(diǎn)。
-
自平衡樹(shù)（Self-balancing Tree）：如 AVL 樹(shù)和紅黑樹(shù)，保持樹(shù)的高度平衡以優(yōu)化查找效率。
-
N 叉樹(shù)（N-ary Tree）：每個(gè)節(jié)點(diǎn)可以有 N 個(gè)子節(jié)點(diǎn)的樹(shù)結(jié)構(gòu)。
-
Trie（前綴樹(shù)）：一種用于存儲(chǔ)字符串的樹(shù)，常用于快速查找和前綴匹配。
二、樹(shù)之操作
1.遍歷
前序遍歷（Pre-order Traversal）：訪問(wèn)根節(jié)點(diǎn) -> 遍歷左子樹(shù) -> 遍歷右子樹(shù)。
// 前序遍歷preOrderTraversal(node) {if (node) {console.log(node.value);this.preOrderTraversal(node.left);this.preOrderTraversal(node.right);}}中序遍歷（In-order Traversal）：遍歷左子樹(shù) -> 訪問(wèn)根節(jié)點(diǎn) -> 遍歷右子樹(shù)（用于 BST 時(shí)可得到排序結(jié)果）。
// 中序遍歷inOrderTraversal(node) {if (node) {this.inOrderTraversal(node.left);console.log(node.value);this.inOrderTraversal(node.right);}}后序遍歷（Post-order Traversal）：遍歷左子樹(shù) -> 遍歷右子樹(shù) -> 訪問(wèn)根節(jié)點(diǎn)。
// 后序遍歷postOrderTraversal(node) {if (node) {this.postOrderTraversal(node.left);this.postOrderTraversal(node.right);console.log(node.value);}}
層序遍歷（Level-order Traversal）：逐層訪問(wèn)樹(shù)的節(jié)點(diǎn)，通常使用隊(duì)列實(shí)現(xiàn)。
// 層序遍歷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.插入和刪除
插入：在二叉搜索樹(shù)中，插入新節(jié)點(diǎn)時(shí)需要找到合適的位置，保證 BST 的性質(zhì)。
// 插入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);}}}刪除：刪除節(jié)點(diǎn)時(shí)可能需要重新調(diào)整樹(shù)結(jié)構(gòu)，以保持樹(shù)的性質(zhì)，尤其在 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 {// 找到要?jiǎng)h除的節(jié)點(diǎn)if (node.left === null && node.right === null) {return null; // 無(wú)子節(jié)點(diǎn)}if (node.left === null) {return node.right; // 只有右子節(jié)點(diǎn)}if (node.right === null) {return node.left; // 只有左子節(jié)點(diǎn)}// 找到右子樹(shù)中的最小節(jié)點(diǎn)const minNode = this.findMinNode(node.right);node.value = minNode.value; // 替換值node.right = this.deleteNode(node.right, minNode.value); // 刪除最小節(jié)點(diǎn)}return node;}3.查找
在樹(shù)中查找節(jié)點(diǎn)的過(guò)程依賴于樹(shù)的性質(zhì)。對(duì)于二叉搜索樹(shù)，可以通過(guò)比較節(jié)點(diǎn)值快速找到目標(biāo)節(jié)點(diǎn)。
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);}三、樹(shù)的力扣算法實(shí)戰(zhàn)
1.144. 二叉樹(shù)的前序遍歷
題目描述：給你二叉樹(shù)的根節(jié)點(diǎn) root ，返回它節(jié)點(diǎn)值的?前序?遍歷。
示例 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]
解題思路：將二叉樹(shù)進(jìn)行先序遍歷（中左右：根節(jié)點(diǎn)->左子樹(shù)->右子樹(shù)）
代碼：
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. 二叉樹(shù)的中序遍歷
題目描述：給定一個(gè)二叉樹(shù)的根節(jié)點(diǎn) root ，返回 它的 中序?遍歷 。
示例 1：
輸入：root = [1,null,2,3] 輸出：[1,3,2]示例 2：
輸入：root = [] 輸出：[]示例 3：
輸入：root = [1] 輸出：[1]
解題思路：將二叉樹(shù)進(jìn)行中序遍歷（左中右：左子樹(shù)->根節(jié)點(diǎn)->右子樹(shù)）
代碼：
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. 二叉樹(shù)的后序遍歷
題目描述：給你一棵二叉樹(shù)的根節(jié)點(diǎn) root ，返回其節(jié)點(diǎn)值的 后序遍歷 。
示例 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]
解題思路：將二叉樹(shù)進(jìn)行中序遍歷（左右中：左子樹(shù)->右子樹(shù)->根節(jié)點(diǎn)）
代碼：
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. 相同的樹(shù)
題目描述：
給你兩棵二叉樹(shù)的根節(jié)點(diǎn) p 和 q ，編寫(xiě)一個(gè)函數(shù)來(lái)檢驗(yàn)這兩棵樹(shù)是否相同。
如果兩個(gè)樹(shù)在結(jié)構(gòu)上相同，并且節(jié)點(diǎn)具有相同的值，則認(rèn)為它們是相同的。
示例 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
?解題思路：首先判斷兩個(gè)節(jié)點(diǎn)是否都為空，是則返回true;如果一個(gè)為空一個(gè)不為空，則返回false，再判斷兩個(gè)節(jié)點(diǎn)的val值是否相同，不同返回false，依次進(jìn)行傳入兩棵樹(shù)的左節(jié)點(diǎn)和右節(jié)點(diǎn)
代碼：
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. 二叉樹(shù)的最大深度
題目描述：
給定一個(gè)二叉樹(shù) root ，返回其最大深度。
二叉樹(shù)的 最大深度 是指從根節(jié)點(diǎn)到最遠(yuǎn)葉子節(jié)點(diǎn)的最長(zhǎng)路徑上的節(jié)點(diǎn)數(shù)。
示例 1：
輸入：root = [3,9,20,null,null,15,7] 輸出：3示例 2：
輸入：root = [1,null,2] 輸出：2
解題思路： 首先判斷樹(shù)是否為空，空則返回0，將樹(shù)放入棧中，以棧的長(zhǎng)度為值進(jìn)行遍歷，將棧的長(zhǎng)度定義一個(gè)值len，每循環(huán)一次計(jì)數(shù)器num+1，len--，依次彈出stack的棧中元素，判斷是否有左右子節(jié)點(diǎn)，在將其壓入棧中，最后返回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
};