樹是一種分層數據的抽象模型
二叉樹
二叉樹中的節點最多只能有兩個子節點，一個是左側子節點，另一個是右側子節點
二叉搜索樹
二叉搜索樹（BST）是二叉樹的一種，但是只允許你在左側節點存儲（比父節點）小的值，在右側節點存儲（比父節點）大的值。
二叉樹的遍歷
中序遍歷是一種以上行順序訪問BST所有節點的遍歷方式，也就是以從最小到最大的順序訪問所有節點中序追歷的一種應用就是對樹進行排序操作
先序遍歷是以優先于后代節點的順序訪問每JJ k個節點的。先序遍歷的一種應用是打印一個結構
化的文檔。
后序遍歷則是先訪問節點的后代節點，再訪問節點本身。后序遍歷的一種應用是計算一個目錄及其子目錄中所有文件所占空間的大小
封裝一個二叉搜索樹
const Compare = {less: -1,bigger: 1,equ:0}class Node{constructor(val){this.val = valthis.left = nullthis.right = null}}class BST{constructor(){this.root = null}insert(val){if(this.root === null){this.root = new Node(val)}else{this.insertNode(this.root,val)}}insertNode(node,val){if(this.compareFn(val,node.val) ===Compare.less){if(node.left === null){node.left = new Node(val)}else{this.insertNode(node.left,val)}}else{if(node.right === null){node.right = new Node(val)}else{this.insertNode(node.right,val)}}}compareFn(a,b){if(a ===b){return Compare.equ}return a <b ? Compare.less : Compare.bigger}inOrderMap(callback){// this.inOrderMapNode(this.root,callback)this.preOrderMapNode(this.root,callback)// this.postOrderMapNode(this.root,callback)}//中序遍歷inOrderMapNode(node,callback){if(node!=null){this.inOrderMapNode(node.left,callback)callback(node.val)this.inOrderMapNode(node.right,callback)}}//先序遍歷preOrderMapNode(node,callback){if(node!=null){callback(node.val)this.preOrderMapNode(node.left,callback)this.preOrderMapNode(node.right,callback)}}//后序遍歷postOrderMapNode(node,callback){callback(node.val)this.postOrderMapNode(node.left,callback)this.postOrderMapNode(node.right,callback)}//最小子節點minNode(){let current = this.rootwhile(current != null && current.left !=null){current = current.left}return current.val}maxNode(){let current = this.rootwhile(current != null && current.right!=null){current = current.right}return current.val}search(val){return this.searchNode(this.root,val)}searchNode(node,val){if(node === null){return false}if(this.compareFn(val,node.val) === Compare.less){return this.searchNode(node.left,val)}else if(this.compareFn(val,node.val) === Compare.bigger){return this.searchNode(node.right,val)}else{return true}}}let myTree = new BST()myTree.insert(100)myTree.insert(110)myTree.insert(80)myTree.insert(90)myTree.insert(70)console.log(myTree)myTree.inOrderMap((val) => {console.log(val)})
相關簡單題
二叉樹的中序遍歷
給定一個二叉樹的根節點?root?，返回?它的?中序?遍歷?。
示例 1：
**輸入：**root = [1,null,2,3]
輸出：[1,3,2]
示例 2：
**輸入：**root = []
輸出：[]
示例 3：
**輸入：**root = [1]
輸出：[1]
var inorderTraversal = function(root) {const ans=[];const dfs=root=>{if(!root){return;}dfs(root.left);ans.push(root.val);dfs(root.right);}dfs(root);return ans;};
二叉樹的最大深度
給定一個二叉樹?root?，返回其最大深度。
二叉樹的?最大深度?是指從根節點到最遠葉子節點的最長路徑上的節點數。
示例 1：
**輸入：**root = [3,9,20,null,null,15,7]
**輸出：**3
示例 2：
**輸入：**root = [1,null,2]
**輸出：**2
提示：
- 樹中節點的數量在?
[0, 104]?區間內。 -100 <= Node.val <= 100
思路：節點不為空時則分別求左右子樹的高度的最大值，同時加?1?表示當前節點的高度，返回該數值
var maxDepth = function(root) {if(!root) {return 0;} else {const left = maxDepth(root.left);const right = maxDepth(root.right);return Math.max(left, right) + 1;}};
翻轉二叉樹
給你一棵二叉樹的根節點?root?，翻轉這棵二叉樹，并返回其根節點。
示例 1：
**輸入：**root = [4,2,7,1,3,6,9]
輸出：[4,7,2,9,6,3,1]
示例 2：
**輸入：**root = [2,1,3]
輸出：[2,3,1]
示例 3：
**輸入：**root = []
輸出：[]
var invertTree = function(root) {if (root === null) {return null;}const left = invertTree(root.left);const right = invertTree(root.right);root.left = right;root.right = left;return root;};
對稱二叉樹
- 對稱二叉樹
給你一個二叉樹的根節點?root?， 檢查它是否軸對稱。
示例 1：
**輸入：**root = [1,2,2,3,4,4,3]
**輸出：**true
示例 2：
**輸入：**root = [1,2,2,null,3,null,3]
**輸出：**false
var isSymmetric = function (root) {function compare(a, b) {if (!a && b || !b && a) return falseif (!a && !b) return trueif (b.val !== a.val) return false// 下面是兩個節點相等的情況，繼續比較子節點// 將a代碼左側與b代碼右側比較const out = compare(a.left, b.right)// 將a代碼右側與b代碼左側比較const int = compare(a.right, b.left)return out && int}return compare(root.left, root.right)
};二叉樹的直徑
給你一棵二叉樹的根節點，返回該樹的?直徑?。
二叉樹的?直徑?是指樹中任意兩個節點之間最長路徑的?長度?。這條路徑可能經過也可能不經過根節點?root?。
兩節點之間路徑的?長度?由它們之間邊數表示。
示例 1：
**輸入：**root = [1,2,3,4,5]
**輸出：**3
**解釋：**3 ，取路徑 [4,2,1,3] 或 [5,2,1,3] 的長度。
示例 2：
**輸入：**root = [1,2]
**輸出：**1
思路:最長直徑就是最深的左子樹加上最深的右子樹
var diameterOfBinaryTree = function (root) {let ans = 0const dfs = (root) => {if (!root) return 0let l = dfs(root.left)let r = dfs(root.right)ans = Math.max(ans, l + r)return Math.max(l, r) + 1}dfs(root)return ans};
將有序數組轉換為二叉搜索樹
給你一個整數數組?nums?，其中元素已經按?升序?排列，請你將其轉換為一棵?
平衡
?二叉搜索樹。
示例 1：
**輸入：**nums = [-10,-3,0,5,9]
輸出：[0,-3,9,-10,null,5]
解釋：[0,-10,5,null,-3,null,9] 也將被視為正確答案：
示例 2：
**輸入：**nums = [1,3]
輸出：[3,1]
解釋：[1,null,3] 和 [3,1] 都是高度平衡二叉搜索樹。
思路：根據二叉搜索樹的特點 使用dfs
var sortedArrayToBST = function(nums) {const dfs = (nums) => {if (nums.length === 0) return null
// 這段代碼將數組 nums 的長度除以 2 得到的結果進行向下取整
let mid = (nums.length / 2) >> 0const root = new TreeNode(nums[mid])root.left = dfs(nums.slice(0, mid))root.right = dfs(nums.slice(mid + 1))return root}return dfs(nums)};
