剑指offer（八）

23. 二叉搜索树的后续遍历序列

输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历的结果。如果是则输出Yes,否则输出No。假设输入的数组的任意两个数字都互不相同。

思路： 在BST中，左子树的值都小于根节点，右子树的值都大于根节点；后续遍历Sequence中，数组末位为树的根节点的值，从后往前遍历，当找到一个Sequence[i]数字小于根节点的时候，i左侧的部分即为左子树，i右侧至根节点的部分为右子树。继续往前遍历，若在左子树部分找到比根节点大的数字，则return false。当左右子树都满足条件，则将左右子树递归判断是否为BST。

public class Solution {
    public boolean isBST(int [] sequence,int head,int tail){
        if(head >= tail) return true;
        int left = tail;
        while((left > head) && (sequence[left - 1] > sequence[tail])) left--;
        for(int i = head; i <= left - 1; i++){
            if(sequence[i] > sequence[tail]) return false;
        }
        return isBST(sequence, head, left - 1) && isBST(sequence, left, tail - 1);
    }
    

    public boolean VerifySquenceOfBST(int [] sequence) {
        if(sequence.length == 0) return false;
        return isBST(sequence, 0, sequence.length-1);
    }
}

24. 二叉树中和为某一值的路径

输入一颗二叉树和一个整数，打印出二叉树中结点值的和为输入整数的所有路径。路径定义为从树的根结点开始往下一直到叶结点所经过的结点形成一条路径。

思路： 从树根开始往下遍历整棵树，每经过一个节点，将target减去这个节点的值，当遍历到叶子节点的时候，若target等于0，则将这条路径加入到输出中；不为0，则回退一步。

import java.util.ArrayList;
/**
public class TreeNode {
    int val = 0;
    TreeNode left = null;
    TreeNode right = null;

    public TreeNode(int val) {
        this.val = val;
    
    }

}
*/
public class Solution {
    private ArrayList<ArrayList<Integer>> output = new ArrayList<ArrayList<Integer>>();
    private ArrayList<Integer> sequence = new ArrayList<Integer>();
    public ArrayList<ArrayList<Integer>> FindPath(TreeNode root,int target) {
        if(root == null) return output;
        sequence.add(root.val);
        target -= root.val;
        if(target == 0 && root.left == null && root.right == null) output.add(new ArrayList<Integer>(sequence));
        FindPath(root.left, target);
        FindPath(root.right, target);
        sequence.remove(sequence.size() -1);
        return output;
    }
}

25. 复杂链表的复制

输入一个复杂链表（每个节点中有节点值，以及两个指针，一个指向下一个节点，另一个特殊指针指向任意一个节点），返回结果为复制后复杂链表的head。（注意，输出结果中请不要返回参数中的节点引用，否则判题程序会直接返回空）

思路： 将链表的每个结点复制，并将自己的next指向该复制的结点，将random指向random.next，由此得到一个完整的复制链表，之后再拆分链表，将基数位的指向下一个基数位，偶数位指向下一个偶数位，即可得到拆分后的复制链表。

/*
public class RandomListNode {
    int label;
    RandomListNode next = null;
    RandomListNode random = null;

    RandomListNode(int label) {
        this.label = label;
    }
}
*/

public class Solution {
    public RandomListNode Clone(RandomListNode pHead){
        if(pHead==null)
            return null;
        RandomListNode pCur = pHead;

        while(pCur!=null){
            RandomListNode node = new RandomListNode(pCur.label);
            node.next = pCur.next;
            pCur.next = node;
            pCur = node.next;
        }
        pCur = pHead;

        while(pCur!=null){
            if(pCur.random!=null)
                pCur.next.random = pCur.random.next;
            pCur = pCur.next.next;
        }
        RandomListNode head = pHead.next;
        RandomListNode cur = head;
        pCur = pHead;

        while(pCur!=null){
            pCur.next = pCur.next.next;
            if(cur.next!=null)
                cur.next = cur.next.next;
            cur = cur.next;
            pCur = pCur.next;
        }
        return head;       
    }
}

26. 二叉搜索树与双向链表

输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的双向链表。要求不能创建任何新的结点，只能调整树中结点指针的指向。

思路： 利用中序遍历的思路，递归至最左的叶子之后往回遍历，head指向当前结点，将head的右孩子连到根节点，根节点左孩子连到head。

/**
public class TreeNode {
    int val = 0;
    TreeNode left = null;
    TreeNode right = null;

    public TreeNode(int val) {
        this.val = val;
    
    }

}
*/

public class Solution {
    TreeNode head = null;
    TreeNode realHead = null;
    public TreeNode Convert(TreeNode pRootOfTree) {
        ConvertSub(pRootOfTree);
        return realHead;
    }
     
    private void ConvertSub(TreeNode pRootOfTree) {
        if(pRootOfTree==null) return;
        ConvertSub(pRootOfTree.left);
        if (head == null) {
            head = pRootOfTree;
            realHead = pRootOfTree;
        } else {
            head.right = pRootOfTree;
            pRootOfTree.left = head;
            head = pRootOfTree;
        }
        ConvertSub(pRootOfTree.right);
    }
}