复杂链表复制与二叉搜索树
一、二叉搜索树的后序遍历
leetcode 面试题33 --- 二叉搜索树的后序遍历序列【中等】
二叉搜索树的后序遍历
题目描述：让我们通过一个整数数组，来判定此数组是否是二叉搜索树的后序遍历结果。
1、解题思路
小白第一次遇到二叉搜索树的时候，是一脸懵逼的~因为本科的《数据结构》没有学好，后来查找了一下百度，了解到二叉搜索树的定义：简言之，二叉搜索树的中序遍历结果就是一个从小到大的排序数组。这样说可能不太形象，换一种说法吧。也就是说，二叉搜索树的每个节点的左子树的所有节点的值都要小于当前节点的值，该节点的右子树的所有元素值都要大于当前节点的值。
那么现在我们回到这道题目中，如果当前给定的数组是一个二叉搜索树，那么二叉搜索树的后序遍历结果会是什么样子呢？我们可以将其类比到下面这个图形当中：
后序二叉搜索遍历
从后向前看，最后面的未节点就是当前树的根节点，我们向前进行遍历，连续的大于未节点的元素都是右子树的节点；当找到一个元素值小于根节点的值的时候（图中的-2），那么此节点（-2）之前的值都是左子树的内容，左子树的所有元素都应该小于未节点的值。所以我们的判断依据就来了。
- 我们从后向前遍历，未节点为
a[end]，如果a[i]>a[end]则继续向前移动指针，i--。 - 如果遇到元素
a[j] < a[end]，则(j+1) ~ (end-1)的所有元素都是未节点a[end]的右子树，然后从0 ~ j的节点都应该是未节点a[end]的左子树。 - 我们继续判断
0 ~ j的元素值是否都小于未节点，如果出现大于未节点的元素，则当前序列不是二叉搜索树的后序遍历序列，直接返回结果。 - 如果我们左右子树都满足要求，则我们继续下一次的迭代循环，判断
a[end-1]作为未节点时，是否满足二叉搜索树的要求，回到上面的1,2,3步骤。 - 最后当所有的节点都判断结束时，则结束循环。
下面我们来看看代码实现吧~
2、代码实现
public boolean verifyPostorder(int[] postorder) {
if(postorder == null || postorder.length == 0) return true;
return help(postorder , 0 , postorder.length - 1);
}
private boolean help(int[] matrix , int start , int end){
if(start > end) return true;
int target = matrix[end];
int mid = end-1;
while(start <= mid && matrix[mid] > target){//寻找左子树与右子树的转折点
mid--;
}
//左侧的值都大于最末端的值，则代表着左侧的值都是右子树，则继续查看右子树是否是二叉搜索树
if(mid < start) return help(matrix , start , end-1);
int index = mid;
while(start <= index && matrix[index] < target ){//查看当前是否是左子树
index--;
}
if(index < start) {//此时代表着在start --- mid的数字都小于target，都是属于左子树
//查看左子树和右子树各自是否为二叉搜索树
return help(matrix , start , mid) && help(matrix , mid + 1 , end -1);
}else{
return false;
}
}
二、复杂链表的复制
leetcode 面试题35 --- 复杂链表的复制【中等】
复杂链表复制
题目描述： 题目给出了一个链表，只是本题的节点与我们之前遇到的节点不太相同，本题中的节点除了有next属性外，还有一个random属性。我们需要完成整个链表的复制。下面我们来看看对于此题的两种解法，尤其是方法二真的可以让你脑洞大开哟~
1、方法一：插入与删除
解题思路：
对于方法一，我们可以将其简单的理解为三个步骤。分别是插入，修改，与删除
- 插入：首先我们可以根据原始链表，将每一个节点都复制一个新的节点，直接插到被复制节点的后面，形成一个冗余节点列表。
- 修改：根据原始链表的顺序，依次修改每个复制的节点的随机值。
- 删除：将复制后的节点的全部相连，断开与原始链表之间的连接关系。
下面这张图片可以作为整个过程的示意图了~
复制解法
代码实现：
public Node copyRandomList(Node head) {
if(head == null) return null;
Node p = head;
while(p != null){//复制next节点
Node newNode = new Node(p.val);
newNode.next = p.next;
p.next = newNode;
p = p.next.next;
}
p = head;
while(p !=null){//复制随机节点
if(p.random != null){
p.next.random = p.random.next;
}
p = p.next.next;
}
Node res = head.next;
Node slow = head.next;
Node fast = head;
fast.next = fast.next.next;//这一步不可缺少，保证第一个复制节点对N N'的分离操作
fast = fast.next;
while(fast != null){//剪枝
slow.next = fast.next;
fast.next = fast.next.next;
slow = slow.next;
fast = fast.next;
}
return res;
}
2、方法二：hashmap解法
解题思路： 我们使用hashMap来完成解题。我们都知道，hashMap中存储的是<key,value>，那么我们可以稍加利用，将key作为原始链表中的每一个节点，将value作为每一个原始链表中节点的复制节点。对于hashMap解法而言，整个过程类似于一个“并行”复制与修改。
我们将所有的复制节点存放在value中以后，我们按照原始链表来对克隆链表进行修改指向。最后获取原始链表head的value值，即为复制链表的头结点，返回此复制链表的头结点即可！
下面即为hashmap解法的整个过程啦~
hashmap解法
代码实现：
public Node copyRandomList(Node head) {
if(head == null) return null;
HashMap<Node,Node> map = new HashMap<>();
Node p = head;
while(p != null){//复制
map.put(p,new Node(p.val));
p = p.next;
}
p = head;
while(p != null){//调整指向
map.get(p).next = map.get(p.next);
map.get(p).random = map.get(p.random);
p = p.next;
}
return map.get(head);
}
腾讯云开发者
