- 二叉树
- 二叉树用于解决什么问题
- 数据的组织与搜索：
- 排序：
- 表达式和计算：
- 图形处理：
- 举例：二叉树的最近公共祖先
- 思路： 排序/排布方式 和 （排序中）当前树和节点的关系
- 举例2：二叉搜索树的最近公共祖先
- 二叉树用于解决什么问题
二叉树
二叉树是一种常见的树状数据结构，它由节点组成，每个节点最多有两个子节点：
- 左子节点
- 右子节点
这两个子节点可以为空，也可以连接到其他节点。二叉树具有以下特点：
- 每个节点最多有两个子节点。
- 左子节点在父节点的左边，右子节点在父节点的右边。
- 子节点可以为空。
下面是一个简单的二叉树例子：
1
/ \
2 3
/ \ / \
4 5 6 7
在这个例子中，数字表示节点的值，箭头表示子节点的连接关系。
根节点是1，它的左子节点是2，右子节点是3。节点2的左子节点是4，右子节点是5。节点3的左子节点是6，右子节点是7。
这就是一个二叉树的示例，每个节点最多有两个子节点，符合二叉树的定义。
更多详细内容，请微信搜索“前端爱好者“， 戳我 查看 。
前端设计的是遍历问题，例如：任意两个节点的最小的祖先
二叉树用于解决什么问题
二叉树是一种数据结构，它由节点组成，每个节点最多有两个子节点：左子节点和右子节点。这种数据结构通常用于解决各种问题，其中包括但不限于：
数据的组织与搜索：
二叉搜索树 (BST) 是一种常见的二叉树，它可以快速进行搜索、插入和删除操作。通过比较节点的值，可以有效地定位数据项，这在数据库索引和搜索引擎等领域很有用。
举例：在一个包含许多单词的二叉搜索树中搜索一个特定的单词，可以快速定位到该单词并提供相关信息。
排序：
二叉树可以用于排序算法中。比如，通过构建二叉搜索树并进行中序遍历，可以获得有序的数据。
举例：对一组数字进行排序，将它们构建成二叉搜索树，然后进行中序遍历，即可得到有序的数字序列。
表达式和计算：
表达式树是一种二叉树，用于表示数学表达式。它可以帮助进行表达式求值和运算。
举例：将数学表达式如"(3 + 4) * 5"表示成对应的二叉树结构，便于进行运算和求值。
图形处理：
在计算机图形学中，二叉树结构可以用来表示场景图或层次结构，例如场景中的物体组织结构。
举例：用二叉树表示一个计算机游戏中的场景，每个节点代表一个物体或者一个场景元素，并用树的结构表示它们之间的层次关系。
这些只是二叉树应用的一部分，它们在各种领域都有广泛的应用。
举例：二叉树的最近公共祖先
给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。
leetcode地址：https://leetcode.cn/problems/lowest-common-ancestor-of-a-binary-tree/
最近公共祖先的定义为：“对于有根树 T 的两个节点 p、q，最近公共祖先表示为一个节点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”
示例 1：
输入：root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1
输出：3
解释：节点 5 和节点 1 的最近公共祖先是节点 3 。
示例 2：
输入：root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4
输出：5
解释：节点 5 和节点 4 的最近公共祖先是节点 5 。因为根据定义最近公共祖先节点可以为节点本身。
示例 3：
输入：root = [1,2], p = 1, q = 2
输出：1
提示：
树中节点数目在范围 [2, 105] 内。
-109 <= Node.val <= 109
所有 Node.val 互不相同 。
p != q
p 和 q 均存在于给定的二叉树中。
思路： 排序/排布方式 和 （排序中）当前树和节点的关系
- 都位于左侧
- 位于两测
递归:
返回当前子树中，p和q 的最近祖先，没有，返回null
1. 当前遍历到p或者 q.不无要往下遍历，返回当前p q
2. 遍历到null，没有p q,返回nul
3. 遍历子树，左子树 右子树 都有结果，返回root
4. 只有其中一个子树有结果 p / q 只在这个子树下返回 null,null
结果：
/**
* Definition for a binary tree node.
* function TreeNode(val) {
* this.val = val;
* this.left = this.right = null;
* }
*/
/**
* @param {TreeNode} root
* @param {TreeNode} p
* @param {TreeNode} q
* @return {TreeNode}
*/
var lowestCommonAncestor = function(root, p, q) {
if(root == null){
return null
}
// 遇到p,遇到q，直接返回当前的节点
if(root ==p || root == q){
return root
}
// 递归操作
const left = lowestCommonAncestor(root.left, p, q)
const right = lowestCommonAncestor(root.right, p, q)
// 如果左子树和右子树都有节点，则返回root
if(left && right) {
return root
}
// 如果左节点没有，则返回右侧子树
if(!left){
return right
}
// 如果右节点没有，则返回左侧子树
if(!right){
return left
}
};
举例2：二叉搜索树的最近公共祖先
leetcode地址：https://leetcode.cn/problems/lowest-common-ancestor-of-a-binary-search-tree/description/
给定一个二叉搜索树, 找到该树中两个指定节点的最近公共祖先。
最近公共祖先的定义为：“对于有根树 T 的两个结点 p、q，最近公共祖先表示为一个结点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”
例如，给定如下二叉搜索树: root = [6,2,8,0,4,7,9,null,null,3,5]
示例 1:
输入: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 8
输出: 6
解释: 节点 2 和节点 8 的最近公共祖先是 6。
示例 2:
输入: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 4
输出: 2
解释: 节点 2 和节点 4 的最近公共祖先是 2, 因为根据定义最近公共祖先节点可以为节点本身。
说明:
所有节点的值都是唯一的。
p、q 为不同节点且均存在于给定的二叉搜索树中。
解答
/**
* Definition for a binary tree node.
* function TreeNode(val) {
* this.val = val;
* this.left = this.right = null;
* }
*/
/**
* @param {TreeNode} root
* @param {TreeNode} p
* @param {TreeNode} q
* @return {TreeNode}
*/
var lowestCommonAncestor = function(root, p, q) {
if(root == null){
return null
}
// 遇到p,遇到q，直接返回当前的节点
if(root ==p || root == q){
return root
}
// 递归操作
const left = lowestCommonAncestor(root.left, p, q)
const right = lowestCommonAncestor(root.right, p, q)
// 如果左子树和右子树都有节点，则返回root
if(left && right) {
return root
}
// 如果左节点没有，则返回右侧子树
if(!left){
return right
}
// 如果右节点没有，则返回左侧子树
if(!right){
return left
}
};
