剑指offer_20230728
剑指 Offer 68 - II. 二叉树的最近公共祖先
题目说明
给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。
百度百科中最近公共祖先的定义为：“对于有根树 T 的两个结点 p、q，最近公共祖先表示为一个结点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”
解题思路1：HashSet&HashMap
- 可以先对树进行遍历，记录下每个节点的父节点，root节点的父节点记为null，存储在HashMap中
- 节点p一层一层的往上爬，追溯所有的祖宗节点并记录在set中
- 对q节点的祖宗节点一层层往上爬，如果在set中出现了说明是他们的最近公共祖先
解题思路2：
设定一个函数findNode对节点进行查找，找到则返回true，没有则返回false。如果第一次在左右子树都分别找到了p和q，则说明该节点是最近的祖宗节点，此后不做更新。
在lowestCommonAncestor方法中也使用中序遍历从底下往上找
但是这个方法的问题就在于每进行一次lowestCommonAncestor都要进行findNode，会导致性能不佳
解题思路3：dfs（最好的）
同样用一个节点ancestor来记录最终找到的最近公共祖先，但只通过dfs来进行遍历。
同样也是遍历左右两边，用boolean记录左右子树有没有找到节点。但是在判定以及返回上非常的有意思
if ((left && right) || (root.val == p.val || root.val == q.val) && (left || right)) {
ancestor = root;
}
return left || right || root.val == p.val || root.val == q.val;
如果左右子树都是true说明p和q分别在左右子树出现了，则当前节点肯定是最近的祖先节点
如果是root.val和p或q的值相等且左右子树有返回true，说明祖宗节点就是p或者q（也就是当前节点）
在返回时，如果left和right为true说明p或q在这个节点的子树下，后两个则说明直接找到了就在当前节点
剑指 Offer 36. 二叉搜索树与双向链表
题目说明
输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的循环双向链表。要求不能创建任何新的节点，只能调整树中节点指针的指向。
解题思路1：链表记录
直接中序遍历获取到所有节点并且记录在ArrayList中，然后再对ArrayList进行遍历来进行左右指针的变换
解题思路2：
通过中序遍历，用head和pre分别记录头节点（只更新一次）和当前节点的上一个节点
public void dfs(Node node) {
if (node == null) {
return;
}
dfs(node.left);
if (pre != null) {
pre.right = node;
}else {
head = node;
}
node.left = pre;
pre = node;
dfs(node.right);
}
一次只针对pre和cur（代码中为node）两个节点进行更新操作，根据二叉搜索树特性采用中序遍历可以保证获得pre一定是cur的上一位
在遍历结束之后，对head和pre（此时定位到末尾了）进行操作，最终返回head
剑指 Offer 26. 树的子结构
题目说明
输入两棵二叉树A和B，判断B是不是A的子结构。(约定空树不是任意一个树的子结构)
B是A的子结构， 即 A中有出现和B相同的结构和节点值。
解题思路
- 首先在主方法中判定A和B是否为null，是的话直接返回false
- 在遍历方法中，如果B为null则说明找到子树了，如果A为null则说明没找到。如果当前两个节点相等则遍历AB的左子树和右子树
- 其余情况返回false
public boolean traversal(TreeNode A, TreeNode B) {
if (B == null) {
return true;
}
if (A == null) {
return false;
}
if (A.val == B.val) {
if (traversal(A.left, B.left) && traversal(A.right, B.right)) {
return true;
}
}
return false;
}