LeetCode题解

链表

No.203--移除链表元素--简单

链接：移除链表元素

代码：

class Solution {
    public ListNode removeElements(ListNode head, int val) {

        if (head == null) return head;
        
        ListNode dummy = new ListNode(-1, head);
        ListNode pre = dummy;
        ListNode cur = head;

        while (cur != null) {
            if (cur.val == val) pre.next = cur.next;
            else pre = cur;
            cur = cur.next;
        }

        return dummy.next;
    }
}

使用虚拟头节点是链表类题目的常见操作，用于解决头节点与其他节点处理细节不一致的问题。虽然不使用虚拟头节点也完全可以解决，但是为了逻辑的一致性，我将统一使用虚拟头节点。
保留当前处理节点cur的上一个节点pre的可访问性通常是有意义的。

No.206--反转链表--简单

链接：反转链表

递归法：

class Solution {
    public ListNode reverseList(ListNode head) {
        if (head == null || head.next == null) return head;
        ListNode last = reverseList(head.next);
        head.next.next = head;
        head.next = null;
        return last;
    } 
}

使用递归，递归函数的作用要明确：输入一个头节点，将此头节点及之后的所有节点反转，返回值是新的头节点。
每一层递归，只需要将当前节点的后面节点其余节点反转，反转后的新的末尾连上当前节点，当前节点的下一节点指向null即可。

迭代法

class Solution {
    public ListNode reverseList(ListNode head) {
        ListNode pre = null;
        ListNode cur = head;
        ListNode next = null;
        while (cur != null) {
            next = cur.next;
            cur.next = pre;
            pre = cur;
            cur = next;
        }
        return pre;
    }
}

仅考虑当前节点cur，要做的无非是将下一跳指向前一节点pre，然后整体往后移动，处理下一个节点。
为了在改变当前节点下一跳之后，还能准确的迭代到原下一节点，需要在改变前提前将下一节点获取到。

No.24--两两交换链表中的节点--中等

链接：两两交换链表中的节点

递归法

class Solution {
    public ListNode swapPairs(ListNode head) {
        if(head == null || head.next == null) return head;
        ListNode next = head.next;
        ListNode newNode = swapPairs(next.next);
        next.next = head;
        head.next = newNode;
        return next;
    }
}

迭代法

class Solution {
  public ListNode swapPairs(ListNode head) {
        ListNode dummy = new ListNode(-1, head);
        ListNode pre = dummy;
        ListNode next;
        ListNode firstCur;
        ListNode secondCur;
        while (pre.next != null && pre.next.next != null) {
            firstCur = pre.next;
            secondCur = firstCur.next;
            next = secondCur.next;
            pre.next = secondCur;
            secondCur.next = firstCur; 
            firstCur.next = next;
            pre = firstCur;
        }
        return dummy.next;  
    }
}

跟之前的思路差不多，可递归可迭代，只不过每次步进两个节点。

No.19--删除链表的倒数第N个节点--中等

链接：删除链表的倒数第 N 个结点

代码：

class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        if (head == null) return head;
        ListNode dummy = new ListNode(-1, head);
        ListNode fast = dummy;
        ListNode slow = dummy;
        while (n-- > 0) fast = fast.next;
        while(fast.next != null) {
            fast = fast.next;
            slow = slow.next;       
        }
        slow.next = slow.next.next;
        return dummy.next;
    }
}

虚拟头节点的使；
快慢指针，快的先走n步；
while中为什么是fast.next != null：这样循环结束时，fast在最后一个节点，slow在倒数第n个节点的前一个，这样才方便删除倒数第n个节点。如果fast指向末尾null，slow刚好到了倒数第n个节点，不方便删除。

No.面试题02.07--链表相交--简单

链接：链表相交

代码：

public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        ListNode A = headA, B = headB;
        while (A != B) {
            A = A != null ? A.next : headB;
            B = B != null ? B.next : headA;
        }
        return A;
    }
}

两个指针从各自头出发，步进1，走完自己的转去另一个链的头继续，两指针相同时，为null说明全走完了没相遇，不为null说明走到了公共节点（总长都是a+b，公共节点之后长度c，两指针一直以同样的速度走，一定会在a+b-c步时相遇）。

No.142--环形链表 II--中等

链接：环形链表 II

代码：

public class Solution {
    public ListNode detectCycle(ListNode head) {
        ListNode fast = head;
        ListNode slow = head;
        while (fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
            if (fast == slow) {
                fast = head;
                while (slow != fast) {
                    fast = fast.next;
                    slow = slow.next;
                }
                return fast;
            }
        }
        return null;
    }
}

快慢指针；
快指针每次走2，慢指针每次走1，第一次相遇后，两指针分别从head和相遇点出发，均每次走1，再次相遇即为环起点；
fast不论任何时候走不下去了（由于null），一定是不存在环。

二叉树

No.226--翻转二叉树--简单

链接：翻转二叉树

递归法：

class Solution {
    public TreeNode invertTree(TreeNode root) {
        if (root == null) return null;
        TreeNode tmp = root.left;
        root.left = invertTree(root.right);
        root.right = invertTree(tmp);
        return root;
    }
}

抽象起来其实每一层都和交换两个变量a和b的值差不多，写法也是借用tmp，三行搞定…只不过变量的值是子树的根节点。

迭代法：

class Solution {
    public TreeNode invertTree(TreeNode root) {
        if (root == null) return null;
        Stack<TreeNode> stack = new Stack<>();
        stack.push(root);
        while (!stack.isEmpty()){
            TreeNode node = stack.pop();
            TreeNode tmp = node.left;
            node.left = node.right;
            node.right = tmp;
            if (node.right != null){
                stack.push(node.right);
            }
            if (node.left != null){
                stack.push(node.left);
            }
        }
        return root;
    }
}

把前序遍历的读值操作改为对当前节点的左右交换操作，遍历完一遍，那么每个节点都刚好被且仅被翻转了一次。

No.101--对称二叉树--简单

链接：对称二叉树

代码：

class Solution {
    public boolean isSymmetric(TreeNode root) {
        if (root == null) return true;
        return recur(root.left, root.right);
    }

    private boolean recur(TreeNode left, TreeNode right) {
        if ((left == null && right != null) || (left != null && right == null)) return false;
        if (left == null && right == null) return true;
        if (left.val != right.val) return false;
        return recur(left.left, right.right) && recur(left.right, right.left);
    }
}

判断一颗树是不是对称二叉树，看看左右子树是否互相对称（注意不是自己对称），而左右两子树互相对称，需要满足三个条件：
- 左右两子树的根节点值一样
- 左子树的左子树和右子树的右子树互相对称
- 左子树的右子树和右子树的左子树互相对称
因此，本题实质上是从第二层开始递归的。
重点是理解两子树互相对称和一个树是对称二叉树的区别。

No.104--二叉树的最大深度--简单

链接：二叉树的最大深度

递归法：

class Solution {
    public int maxDepth(TreeNode root) {
        if (root == null) return 0;
        return Math.max(maxDepth(root.left), maxDepth(root.right)) + 1;
    }
}

二叉树的最大深度，就是左右子树最大深度的大者+1.

No.111--二叉树的最小深度--简单

链接：二叉树的最小深度

递归法：

class Solution {
    public int minDepth(TreeNode root) {
        if (root == null) return 0;
        int leftDepth = minDepth(root.left);
        int rightDepth = minDepth(root.right);
        if (root.left == null) {
            return rightDepth + 1;
        }
        if (root.right == null) {
            return leftDepth + 1;
        }
        return Math.min(leftDepth, rightDepth) + 1;
    }
}

与No.104题类似，但是不能直接简单的把max换成min，如果某个子树小到极限0，意味着这边不是叶子节点，结果仅有另一边决定。

No.222--完全二叉树的节点个数--中等

链接：完全二叉树的节点个数

代码：

class Solution {
    public int countNodes(TreeNode root) {
        if (root == null) return 0;
        TreeNode left = root.left;
        TreeNode right = root.right;
        int leftDepth = 0, rightDepth = 0; 
        while (left != null) {
            left = left.left;
            leftDepth++;
        }
        while (right != null) {
            right = right.right;
            rightDepth++;
        }
        if (leftDepth == rightDepth) {
            return (2 << leftDepth) - 1;
        }
        return countNodes(root.left) + countNodes(root.right) + 1;
    }
}

为提高计算效率，要充分利用完全二叉树的特性，因此不再考虑常规二叉树计算节点个数的办法；
完全二叉树可以拆分成多个满二叉树，而满二叉树可以直接根据层数计算节点个数；
因此，从根节点开始递归，递归过程中，若当前二叉树是满二叉树直接计算，不是的话继续拆分；
判断是满二叉树，就看一路向左和一路向右的路是否一样长（前提是已知是完全二叉树）。

No.110--平衡二叉树--简单

这真能算简单？

链接：平衡二叉树

自顶向下递归：

class Solution {
    public boolean isBalanced(TreeNode root) {
        if (root == null) return true;
        return isBalanced(root.left) && isBalanced(root.right) && Math.abs(height(root.left) - height(root.right)) <= 1;
    }

    private int height(TreeNode root) {
        if (root == null) return 0;
        return Math.max(height(root.left), height(root.right)) + 1;
    }
}

这种递归比较好理解，与平衡二叉树的定义完全一致，但是存在重复计算。不同的isBalanced调用中，对同一个节点的height计算是重复的，可以优化为如下自底向上的递归过程。

自底向上递归：

class Solution {
    public boolean isBalanced(TreeNode root) {
        return height(root) >= 0;
    }

    public int height(TreeNode root) {
        if (root == null) {
            return 0;
        }
        int leftHeight = height(root.left);
        int rightHeight = height(root.right);
        if (leftHeight == -1 || rightHeight == -1 || Math.abs(leftHeight - rightHeight) > 1) {
            return -1;
        } else {
            return Math.max(leftHeight, rightHeight) + 1;
        }
    }
}

这种递归，只有一个height函数是在递归调用的，递归的过程本质上是自底向上推出每一个节点的高度，不存在重复计算。
在这一过程中捎带地判断是否平衡是很有必要的，仅仅知道左右子树高度、而不知道左右子树是否平衡，是不足以判断当前树是否平衡的。

No.257--二叉树的所有路径--简单

这还是简单？

链接：二叉树的所有路径

代码：

class Solution {

    List<String> result = new ArrayList<>();

    public List<String> binaryTreePaths(TreeNode root) {
        recur(root, "");
        return result;
    }

    public void recur(TreeNode node, String s) {
        if (node == null)
            return;
        if (node.left == null && node.right == null) {
            result.add(new StringBuilder(s).append(node.val).toString());
            return;
        }
        String tmp = new StringBuilder(s).append(node.val).append("->").toString();
        recur(node.left, tmp);
        recur(node.right, tmp);
    }
}

这是递归法一种比较简单的写法，之前的状态不用全局变量来维护，而是直接用一个新的值传进来，这样不用考虑回溯之后撤销影响的问题，每次传到一次递归调用的，都是目前已知路径的一个新变量tmp。
此处递归函数的含义：当前处理节点root，从原根节点到目前节点之父的路径已知是s，该如何操作，即：把当前节点拼到串上，生成作为已知路径，剩下的交给左孩子和右孩子分别处理。

链接：移除链表元素

代码：

链接：反转链表

递归法：

迭代法

链接： 两两交换链表中的节点

递归法

迭代法

链接：删除链表的倒数第 N 个结点

代码：

链接：链表相交

代码：

链接：环形链表 II

代码：

链接：翻转二叉树

递归法：

迭代法：

链接：对称二叉树

代码：

链接：二叉树的最大深度

递归法：

链接：二叉树的最小深度

递归法：

链接：完全二叉树的节点个数

代码：

链接：平衡二叉树

自顶向下递归：

自底向上递归：

链接：二叉树的所有路径

代码：

链接：两两交换链表中的节点