【剣指offer】コードを手でちぎる(3)

21、min関数を含むスタック:

はスタックのデータ構造を定義し、スタックの最小要素を得ることができるmin関数をタイプで実現し、push、pop、minを呼び出す時間の複雑さはO(1)

である.

public class Test {
    Stack<Integer> stack = new Stack<>();
    public void push(int node) {
        stack.push(node);
    }
    public void pop() {
        stack.pop();
    }
    public int top() {
        //     
        return stack.peek();
    }
    public int min() {
        int temp = 0;
        int min = stack.peek();
        //   
        Iterator<Integer> it = stack.iterator();
        //             
        while(it.hasNext()){
            temp = it.next();
            if(min > temp){
                min = temp;
            }
        }
        return min;
    }
    public static void main(String[] args) {
        Test test = new Test();
        test.push(1);
        test.push(2);
        test.push(3);
        test.push(4);
        test.push(5);
        test.pop();
        System.out.println(test.top());
        System.out.println(test.min());
    }
}

22、スタックの圧入、ポップアップシーケンス:2つの整数シーケンスを入力し、最初はスタック圧入であり、2番目はスタックポップアップであるかどうかを判断する.

public class Test{
    public boolean isPopOrder(int[] arr1,int[] arr2){
        if (arr1==null || arr2==null || arr1.length==0 || arr2.length==0)
            return false;
        Stack<Integer> stack = new Stack<Integer>();
        for (int i=0;i<arr1.length;i++){
            stack.push(arr1[i]);
        }
        //               
        for (int i=0;i<arr2.length;i++){
            //                           ，   
            if (!stack.isEmpty() && stack.peek()==arr2[i]){
                stack.pop();
            }else {
                //        ，     ，  
                if (stack.isEmpty()){
                    return true;
                }else {
                    //           
                    return false;
                }
            }
        }
        return true;
    }
    public static void main(String[] args) {
        int[] line1 = {1,2,3,4,5};
        int[] line2 = {5,4,3,2,1};
        int[] line3 = {4,3,5,1,2};
        int[] line4 = new int[10];
        int[] line5 = {};
        Test test = new Test();
        System.out.println(test.isPopOrder(line1,line2));
    }
}

23、二叉の木を上から下に印刷し、同じ層のノードは左から右へ順に巡回します.

class BinaryTreeNode {
    public int value;
    public BinaryTreeNode leftNode;
    public BinaryTreeNode rightNode;
    public BinaryTreeNode(int value) {
        this.value = value;
    }
    @Override
    public String toString() {
        return "BinaryTreeNode [data=" + value + ", left=" + leftNode + ", right=" + rightNode
                + "]";
    }
}
public class Test{
    public static void main(String[] args) {
        BinaryTreeNode root1 = new BinaryTreeNode(8);
        BinaryTreeNode node1 = new BinaryTreeNode(8);
        BinaryTreeNode node2 = new BinaryTreeNode(7);
        BinaryTreeNode node3 = new BinaryTreeNode(9);
        BinaryTreeNode node4 = new BinaryTreeNode(2);
        BinaryTreeNode node5 = new BinaryTreeNode(4);
        BinaryTreeNode node6 = new BinaryTreeNode(7);
        root1.leftNode=node1;
        root1.rightNode=node2;
        node1.leftNode=node3;
        node1.rightNode=node4;
        node4.leftNode=node5;
        node4.rightNode=node6;
        Test test = new Test();
        test.printFromTopToBottom(root1).toString();
    }
    private ArrayList<Integer> printFromTopToBottom(BinaryTreeNode root1) {
        //list             
        ArrayList list = new ArrayList();
        //     
        if (root1==null)
            return list;
        //        
        Queue<BinaryTreeNode> queue = new LinkedList<BinaryTreeNode>();
        queue.offer(root1);
        //         
        while (!queue.isEmpty()){
            BinaryTreeNode node = queue.poll();
            if (node.leftNode!=null){
                queue.offer(root1.leftNode);
            }
            if (node.rightNode!=null){
                queue.offer(root1.rightNode);
            }
            list.add(node.value);
        }
        return list;
    }
}

24、二叉検索ツリーの後序はシーケンスを巡回します.

二叉並び替えツリー(Binary Sort Tree)は、二叉検索ツリーとも呼ばれています.

二叉サーチツリーの特徴:左は全部ルートより小さいです.右のは全部ルートより大きいです.左右に分かれても元素は重複できません.

は、ある二叉の木を検索した後、順番に結果を巡回したかどうかを判断する整数配列を入力し、trueとfalse

を返します.

二叉樹の後端を巡回する特徴:最後の要素はルートノードで、“左右の中”は

を巡回します.

public class Test{
    public boolean verifySequenceOfBST(int[] sequence){
        if (sequence==null || sequence.length==0){
            return false;
        }
        //       ，      sequence  
        //                       
        int length = sequence.length;
        int root = sequence[length-1];
        int cut = 0;
        //    ,          
        for (int i = 0; i < length -1; i++) {
            if (sequence[i]>root){
                //   
                cut = i+1;
                break;
            }
        }
        //        ，         
        if (cut==0){
            verifySequenceOfBST(Arrays.copyOfRange(sequence,0,length-1));
        }else {
            //       ，                   
            for (int j = cut;j<length-1;j++){
                if (sequence[j]<root)
                    return false;
            }
        }
        //         
        boolean left = true;
        if (cut>0){
            left = verifySequenceOfBST(Arrays.copyOfRange(sequence,0,cut));
        }
        boolean right = true;
        if (cut<length-1){
            right = verifySequenceOfBST(Arrays.copyOfRange(sequence,cut,length-1));
        }
        return (right&&left);
    }
    public static void main(String[] args) {
        Test test = new Test();
        int[] arr = {5,7,6,9,11,10,8};
        System.out.println(test.verifySequenceOfBST(arr));
    }
}

25、二叉樹と中和のいずれかの値の経路:木のルートノードから葉っぱノードに至るまでのノードが一つの経路を形成する.

class BinaryTreeNode{
    BinaryTreeNode left;
    BinaryTreeNode right;
    int value;
    public BinaryTreeNode(int value){
        this.value = value;
    }
}
public class Test{
    public void findPath(BinaryTreeNode root,int sum){
        if (root == null)
            return;
        Stack<Integer> stack = new Stack<Integer>();
        int currentSum = 0;
        findPath(root,sum,currentSum,stack);
    }
    private void findPath(BinaryTreeNode root, int sum, int currentSum,Stack<Integer> stack) {
        currentSum += root.value;
        stack.push(root.value);
        if (root.left==null && root.right==null){
            if (currentSum == sum){
                System.out.println("      ");
                for (int path:stack){
                    System.out.println(path+" ");
                }
                System.out.println( );
            }
        }
        if (root.left!=null)
            findPath(root.left,sum,currentSum,stack);
        if (root.right!=null)
            findPath(root.right,sum,currentSum,stack);
        stack.pop();
    }
    public static void main(String[] args) {
        BinaryTreeNode root1 = new BinaryTreeNode(10);
        BinaryTreeNode node1 = new BinaryTreeNode(5);
        BinaryTreeNode node2 = new BinaryTreeNode(12);
        BinaryTreeNode node3 = new BinaryTreeNode(4);
        BinaryTreeNode node4 = new BinaryTreeNode(7);
        root1.left=node1;
        root1.right=node2;
        node1.left=node3;
        node1.right=node4;
        Test test = new Test();
        test.findPath(root1,22);
    }
}