一个网站的tdk是指网站的,吴江企业网站建设,同个主体新增网站备案,一个人做公司管理网站目录 一、树#xff08;Tree#xff09;
1.介绍
2.特点
3.基本术语
4.种类
二、树之操作
1.遍历
前序遍历#xff08;Pre-order Traversal#xff09;#xff1a;访问根节点 - 遍历左子树 - 遍历右子树。
中序遍历#xff08;In-order Traversal#xf…目录 一、树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每循环一次计数器num1len--依次弹出stack的栈中元素判断是否有左右子节点在将其压入栈中最后返回num值
代码
var maxDepth function(root) {if(!root) return 0const stack [root]let num 0while(stack.length){let len stack.lengthnumwhile(len--){const o stack.shift()o.left stack.push(o.left)o.right stack.push(o.right)}}return num
};
