基础新手

链表

注意事项

注意保存上下文环境。注意gc，不要有垃圾变量。换头结点注意考虑头

对于链表不要在乎是O(n)还是O(2n)

长短链表互换

习题

K个节点的组内逆序调整 ?

leetcode：K 个一组翻转链表

找n函数

逆转函数

第一组是否找齐

之后每组处理：start先指向下一组头，遍历完再指向尾

不在于算法，而在于coding能力

注意长短链表互换，链表1结点+链表2结点+进位，注意最后进位需要补结点

阶段1：两个相加+进位 while(shortNode != null)

阶段2：单个链表+进位 while(longNode != null)

阶段3：链表结束，仍有进位，补结点 if(carry != 0)

上面三个阶段分别是3个循环

有序链表合并

注意换头，有一个为空就出循环

合并K个升序链表

leetcode:合并K个升序链表

利用小根堆，注意返回空

m条链表，总结点n个。时间复制度 O(log(m)*n)

class Solution {
    class PackageNode {
        ListNode node;
        Integer index;
        public PackageNode(ListNode node, Integer index) {
            this.node = node;
            this.index = index;
        }
    }
    public ListNode mergeKLists(ListNode[] lists) {
        if (lists.length == 0) {
            return null;
        }
        ListNode head = null;
        ListNode p = head;
        PriorityQueue<PackageNode> priorityQueue = new PriorityQueue<>(lists.length, Comparator.comparingInt(a -> a.node.val));
        for (int i = 0; i < lists.length; i++) {
            if (lists[i] != null) {
                priorityQueue.add(new PackageNode(lists[i], i));
                lists[i] = lists[i].next;
            }
        }
        while (priorityQueue.size() > 0) {
            PackageNode packageNode = priorityQueue.poll();
            Integer index = packageNode.index;
            if (lists[index] != null) {
                priorityQueue.add(new PackageNode(lists[index], index));
                lists[index] = lists[index].next;
            }
            if (head == null) {
                head = packageNode.node;
                p = head;
            } else {
                p.next = packageNode.node;
                p = p.next;
            }
        }
        return head;
    }
}

树

注意事项

对于全都遍历的，使用递归很方便

习题

判断两棵树是否相同

leetcode:相同的树

注意异或^的使用，只有一个成立时为真

对于全都遍历的，使用递归很方便！！！

class Solution {
    public boolean isSameTree(TreeNode p, TreeNode q) {
        ArrayList<TreeNode> list1 = new ArrayList<>();
        ArrayList<TreeNode> list2 = new ArrayList<>();
        list1.add(p);
        list2.add(q);
        while (!list1.isEmpty() && !list2.isEmpty()) {
            p = list1.remove(0);
            q = list2.remove(0);
            if (p == null && q == null) {
                continue;
            } else if (p != null ^ q != null) {
                return false;
            }
            if (p.val != q.val) {
                return false;
            }
            if (p.left != null && q.left != null) {
                list1.add(p.left);
                list2.add(q.left);
            } else if (p.left == null ^ q.left == null) {
                return false;
            }
            if (p.right != null && q.right != null) {
                list1.add(p.right);
                list2.add(q.right);
            } else if (p.right == null ^ q.right == null) {
                return false;
            }
        }
        return list1.isEmpty() && list2.isEmpty();
    }
}

判断树是否是镜面树

leetcode:对称二叉树

虽然是简单，但是也做了不少时间

传两个头结点(left,right)！！！我又用了层序遍历

判断left.val == right.val && fun(left.left, right.right) && fun(left.right, right.left)

class Solution {
    public boolean isSymmetric(TreeNode root) {
        return isSymmetric(root, root);
    }
    public boolean isSymmetric(TreeNode p, TreeNode q) {
        if (p == null ^ q == null) {
            return false;
        }
        if (p == null && q == null) {
            return true;
        }
        return p.val == q.val && isSymmetric(p.left, q.right) && isSymmetric(p.right, q.left);
    }
    public boolean isSymmetricLevel(TreeNode root) {
        if (root == null) {
            return true;
        }
        ArrayList<TreeNode> treeList = new ArrayList<>();
        treeList.add(root);
        while (!treeList.isEmpty()) {
            if (treeList.size() > 1 && (treeList.size() & 1) != 0) {
                return false;
            }
            int len = treeList.size();
            for (int i = 0; i < len >> 1; i++) {
                int leftIndex = len - i - 1;
                if (treeList.get(i) == null ^ treeList.get(leftIndex) == null) {
                    return false;
                }
                if (treeList.get(i) == null && treeList.get(leftIndex) == null) {
                    continue;
                }
                if (treeList.get(i).val != treeList.get(leftIndex).val) {
                    return false;
                }
                treeList.add(treeList.get(i).left);
                treeList.add(treeList.get(i).right);
            }
            for (int i = len >> 1; i < len; i++) {
                if (treeList.get(i) == null) {
                    continue;
                }
                treeList.add(treeList.get(i).left);
                treeList.add(treeList.get(i).right);
            }
            for (int i = 0; i < len; i++) {
                treeList.remove(0);
            }
        }
        return true;
    }
}

返回树的最大深度

leetcode:二叉树的最大深度

用递归思想代码十分简单。差点又想用层序
class Solution {
    public int maxDepth(TreeNode root) {
        if (root == null) {
            return 0;
        }
        return 1 + Math.max(maxDepth(root.left), maxDepth(root.right));
    }
}

先序遍历和中序遍历建树

leetcode:从前序与中序遍历序列构造二叉树

没啥说的，常见题

    class Solution {
        HashMap<Integer, Integer> numSite = new HashMap<>();
        public TreeNode buildTree(int[] preorder, int[] inorder) {
            if (preorder.length <= 0) {
                return null;
            }
            for (int i = 0; i < inorder.length; i++) {
                numSite.put(inorder[i], i);
            }
            return buildTree(preorder, 0, preorder.length - 1, inorder, 0, inorder.length - 1);
        }
        public TreeNode buildTree(int[] preorder, int preLow, int preHigh, int[] inorder, int inLow, int inHigh) {
            if (preLow > preHigh) {
                return null;
            }
            TreeNode head = new TreeNode(preorder[preLow]);
            if (preLow < preHigh) {
                int index = numSite.get(head.val);
                head.left = buildTree(preorder, preLow + 1, preLow + (index - inLow), inorder, inLow, index - 1);
                head.right = buildTree(preorder, preLow + (index - inLow) + 1, preHigh, inorder, index + 1, inHigh);
            }
            return head;
        }
    }