26、29、35

劍指 Offer 26. 樹的子結構

思路一就是遞回啊、不必將遞回想的太清楚、交給系統的堆疊去完成🤣、首先要判斷兩棵樹是不是相等的：如果當前的B的節點的值等于A節點的值的話、那么就分別去看B的左和A的左是不是相等、看B的右和A的右是不是相等、直到B為null的時候、說明A和B兩棵樹相等、如果中途A走完或者A的值不等于B的值的話、那么回傳false，
B是A的子樹就是要把A的每一個節點作為根和B去判斷是不是相等的、先判斷A的根、再是A的left、再是A的right、如果有一個可以找到就回傳true.
思路二就是bfs、思路和上面的思路是一樣的、只不過是樹遍歷的方式b不同罷了、只是借助佇列實作了樹的遍歷而已.

    //思路一
    public boolean isSubStructure(TreeNode A, TreeNode B) {
        if (A == null || B == null) return false;

        return isSameTree(A, B) || isSubStructure(A.left, B) || isSubStructure(A.right, B);
    }

    public boolean isSameTree(TreeNode A, TreeNode B) {
        if (B == null) return true;

        if (A == null || A.val != B.val) return false;

        return isSubTree(A.left, B.left) && isSubTree(A.right, B.right);
    }


    //思路二
    public boolean isSubStructure(TreeNode A, TreeNode B) {
        if (A == null || B == null) return false;
        Queue<TreeNode> queue = new LinkedList<>();

        queue.offer(A);
        while (!queue.isEmpty()) {
            TreeNode cur = queue.poll();
            if (cur.val == B.val) {
                if (helper(cur, B)) {
                    return true;
                }
            }

            if (cur.left != null) {
                queue.offer(cur.left);
            }
            if (cur.right != null) {
                queue.offer(cur.right);
            }
        }

        return false;
    }

    public boolean helper(TreeNode A, TreeNode B) {
        Queue<TreeNode> queueA = new LinkedList<>();
        Queue<TreeNode> queueB = new LinkedList<>();
        queueA.offer(A);
        queueB.offer(B);

        while (!queueB.isEmpty()) {
            TreeNode curB = queueB.poll();
            TreeNode curA = queueA.poll();
            if (curA == null || curA.val != curB.val) {
                return false;
            }

            if (curB.left != null) {
                queueA.offer(curA.left);
                queueB.offer(curB.left);
            }
            if (curB.right != null) {
                queueA.offer(curA.right);
                queueB.offer(curB.right);
            }
        }

        return true;
    }

劍指 Offer 29. 順時針列印矩陣

思路就是順時針列印、要注意上下左右四個方向、不能越界、每次列印完一個回圈的時候、對應的左邊界、右邊界、上邊界、或者下邊界其中一個會增加或者減少、如果左邊界大于右邊界的話或者上邊界大于下邊界的話、那么也就遍歷完陣列了，

    public int[] spiralOrder(int[][] matrix) {
        int left = 0;
        int right = matrix[0].length - 1;
        int top = 0;
        int button = matrix.length - 1;
        int[] res = new int[(right + 1) * (button + 1)];
        int resIndex = 0;
        while (true) {
            for (int i = left; i <= right; i++) {
                res[resIndex++] = matrix[top][i];
            }
            if (++top > button) break;
            for (int i = top; i <= button; i++) {
                res[resIndex++] = matrix[i][right];
            }
            if (--right < left) break;
            for (int i = right; i >= left; i--) {
                res[resIndex++] = matrix[button][i];
            }
            if (--button < top) break;
            for (int i = button; i >= top; i--) {
                res[resIndex++] = matrix[i][left];
            }
            if (++left > right) break;
        }

        return res;
    }

劍指 Offer 35. 復雜鏈表的復制

思路一：將節點存盤在hash 表中、鍵和值都是自己、復制的時候、就可以取出對應的值了，
思路二：三次遍歷、第一次在原有的節點的后面加上本身復制的節點、原有節點的next是自己的復制節點、自己的復制節點的next是自己的next，第二次遍歷將復制節點的random 指向原節點的random.next、因為當前的節點的next都是自己的復制節點、第三次的遍歷就是將所有的復制節點連接起來、pre為head、cur為head.next、pre.next = pre.next.next; cur.next = cur.next.next; pre = pre.next;cur = cur.next;這樣就將所有的復制節點串聯起來了、最后將復制鏈表的next置為null.

    //思路一
    public Node copyRandomList(Node head) {
        if (head == null) return null;
        Node cur = head;
        HashMap<Node, Node> hashMap = new HashMap<>();
        while (cur != null) {
            hashMap.put(cur, new Node(cur.val));
            cur = cur.next;
        }
        cur = head;
        while (cur != null) {
            hashMap.get(cur).next = hashMap.get(cur.next);
            hashMap.get(cur).random = hashMap.get(cur.random);
            cur = cur.next;
        }

        return hashMap.get(head);
    }

    //思路二
    public Node copyRandomList(Node head) {
        if (head == null) return null;
        Node cur = head;
        while (cur != null) {
            Node newCur = new Node(cur.val);
            newCur.next = cur.next;
            cur.next = newCur;
            cur = newCur.next;
        }

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

        }

        Node pre = head;
        Node res = head.next;
        cur = head.next;
        while (cur.next != null) {
            pre.next = pre.next.next;
            cur.next = cur.next.next;
            pre = pre.next;
            cur = cur.next;
        }

        pre.next = null;
        return res;
    }