今天来学习以下几道《剑指offer》里有关数据结构的算法题
从尾到头打印链表用两个栈实现队列重建二叉树二叉树的下一个节点
从尾到头打印链表
输入个链表的头结点，从尾到头反过来打印出每个结点的值。
很容易可以想到使用栈或者递归来实现
代码实现
public class Test {
public static class ListNode{
int val;
ListNode next;
}
//—---------使用栈----------
public static void printListReverseUsStack(ListNode root){
Stack<ListNode> stack=new Stack<>();
while(root!=null){
stack.push(root);
root=root.next;
}
ListNode temp;
while(!stack.isEmpty()){
temp=stack.pop();
System.out.print(temp.val+" ");
}
}
//—---------使用递归-------------
public static void printListReverseUsRecursion(ListNode root){
if (root!=null) {
if (root.next!=null) {
printListReverseUsDiGui(root.next);
}
}
System.out.print(root.val+" ");
}
}用两个栈实现队列
用两个栈实现一个队列。队列的声明如下，请实现它的两个函数appendTail 和deleteHead， 分别完成在队列尾部插入结点和在队列头部删除结点的功能。
解题思路
(1)插入：将元素压入到stack1中。
(2)删除：当stack2不为空时，弹出stack2的栈顶元素。 当stack2为空时，将stack1的元素逐个弹出并压入到stack2中，然后弹出栈顶元素。
代码实现
public class CQueue<T>{
private Stack<T> stack1=new Stack<>();
private Stack<T> stack2=new Stack<>();
//尾部添加
public void appendTail(T t){
stack1.push(t);
}
//删除头部
public T deleteHead(){
if (stack2.isEmpty()){
while (!stack1.isEmpty()){
stack2.push(stack1.pop());
}
}
if (stack2.isEmpty()) throw new RuntimeException("No Data!");
return stack2.pop();
}
}重建二叉树
输入某二叉树的前序遍历和中序遍历的结果，请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。
解题思路
(1)前序遍历的第一个数字就是根结点的值。
(2)扫描中序遍历中根结点的位置，根结点左边的值为左子树结点的值，右边的为右子树结点的值。
(3)既然我们已经分别找到了左、右子树的前序遍历和中序遍历，接下来可以递归地构建左、右子树。
代码实现
public class BinaryTree {
public static class BinaryTreeNode {
int value;
BinaryTreeNode left;
BinaryTreeNode right;
}
//preorder和inorder分别为前序遍历和后序遍历
public static BinaryTreeNode construct(int[] preorder, int[] inorder) {
// 输入的合法性判断，两个数组都不能为空，并且都有数据，而且数据的数目相同
if (preorder == null || inorder == null || preorder.length != inorder.length || inorder.length < 1) {
return null;
}
return construct(preorder, 0, preorder.length - 1, inorder, 0, inorder.length - 1);
}
/**
* @param preorder 前序遍历
* @param ps 前序遍历的开始位置
* @param pe 前序遍历的结束位置
* @param inorder 中序遍历
* @param is 中序遍历的开始位置
* @param ie 中序遍历的结束位置
* @return 树的根结点
*/
public static BinaryTreeNode construct(int[] preorder, int ps, int pe, int[] inorder, int is, int ie) {
// 开始位置大于结束位置说明已经没有需要处理的元素了
if (ps > pe) {
return null;
}
// 取前序遍历的第一个数字，就是当前的根结点
int value = preorder[ps];
int index = is;
// 在中序遍历的数组中找根结点的位置
while (index <= ie && inorder[index] != value) {
index++;
}
// 如果在整个中序遍历的数组中没有找到，说明输入的参数是不合法的，抛出异常
if (index > ie) {
throw new RuntimeException("Invalid input");
}
// 创建当前的根结点，并且为结点赋值
BinaryTreeNode node = new BinaryTreeNode();
node.value = value;
// 递归构建当前根结点的左子树，左子树的元素个数：index-is个
// 左子树对应的前序遍历的位置在[ps+1, ps+index-is]
// 左子树对应的中序遍历的位置在[is, index-1]
node.left = construct(preorder, ps + 1, ps + index - is, inorder, is, index - 1);
// 递归构建当前根结点的右子树，右子树的元素个数：ie-index个
// 右子树对应的前序遍历的位置在[ps+index-is+1, pe]
// 右子树对应的中序遍历的位置在[index+1, ie]
node.right = construct(preorder, ps + index - is + 1, pe, inorder, index + 1, ie);
return node;
}
}二叉树的下一个节点
给定一个二叉树和其中的一个结点，请找出中序遍历顺序的下一个结点并且返回。 注意，树中的结点不仅包含左右子结点，同时包含指向父结点的指针。
解题思路
(1)如果一个结点有右子树，那么它的下一个结点就是它的右子树的最左子结点。 例如，图中结点b的下一个结点是h。
(2)接着我们分析一下结点没有右子树的情形。如果结点是它父结点的左子结点，那么它的下一个结点就是它的父结点。 例如，结点d的下一个结点是b。
(3)如果一个结点既没有右子树，并且它还是父结点的右子结点，这种情形就比较复杂。 我们可以沿着指向父结点的指针一直向上遍历，直到找到一个是它父结点的左子结点的结点。 如果这样的结点存在，那么这个结点的父结点就是我们要找的下一个结点。 例如结点i的下一个结点是a。
代码实现
public class Solution {
public class BinaryTreeNode {
int val;
TreeLinkNode left;
TreeLinkNode right;
TreeLinkNode parent;
}
public TreeLinkNode getNext(BinaryTreeNode pNode){
BinaryTreeNode curNode;
//第一步：判断是否有右孩子
if(pNode.right != null){
curNode = pNode.right;
while(curNode.left != null) curNode = curNode.left;
return curNode;
}
//第二步：判断是否是其父节点的左孩子
if(pNode.parent == null) return null;
if(pNode == pNode.parent.left){
return pNode.parent;
}
//第三步：向上找其父节点，直到父节点是其父节点的的左子节点
curNode = pNode.parent;
while(curNode.parent != null){
if(curNode == curNode.parent.left){
return curNode.parent;
}
//继续向上找父节点
curNode = curNode.parent;
}
return null;
}
}
发表回复