1.1. 基本结构


1.1.1. 二叉树

二叉树是一种常用的数据结构,它的逻辑简单:除根节点外每个节点都有一个父节点,根节点没有父节点;除叶子节点外,所有节点都有一个或者多个子节点,叶子节点没有子节点。面试中出现的树结构,一般都是二叉树结构。在二叉树中,最重要几种遍历方式:

  • 前序遍历:根节点 >> 左节点 >> 右节点 10>>6>>4>>8>>14>>12>>16
  • 中序遍历:左节点 >> 根节点 >> 右节点 4>>6>>8>>10>>12>>14>>16
  • 后序遍历:左节点 >> 右节点 >> 根节点 4>>8>>6>>12>>16>>14>>10

PS:必须对这三种遍历方式的六种实现了如指掌(递归+遍历)

import java.util.ArrayList;
public class Main {
    public static void main(String[] args) {
        Tree tree = new Tree();
        tree.initTree();
        //前序
        ArrayList<Integer> prelist = new ArrayList<>();
        prelist = tree.preOrder(tree.getRoot(),prelist);
        System.out.println("前序:"+prelist);
        //前序-非递归
        ArrayList<Integer> prelist2 = new ArrayList<>();
        prelist2 = tree.preOrder2(tree.getRoot(),prelist2);
        System.out.println("前序:"+prelist2);
        //中序
        ArrayList<Integer> inlist = new ArrayList<>();
        inlist = tree.inOrder(tree.getRoot(),inlist);
        System.out.println("中序:"+inlist);
        //中序-非递归
        ArrayList<Integer> inlist2 = new ArrayList<>();
        inlist2 = tree.inOrder(tree.getRoot(),inlist2);
        System.out.println("中序:"+inlist2);
        //后序
        ArrayList<Integer> postlist = new ArrayList<>();
        postlist = tree.postOrder(tree.getRoot(),postlist);
        System.out.println("后续:"+postlist);
        //后序-非递归
        ArrayList<Integer> postlist2 = new ArrayList<>();
        postlist2 = tree.postOrder2(tree.getRoot(),postlist2);
        System.out.println("后续:"+postlist2);

    }
}

import java.util.ArrayList;
import java.util.LinkedList;
public class Tree {
    private BinaryTreeNode root;
    public class BinaryTreeNode{
        private BinaryTreeNode llink = null;
        private BinaryTreeNode rlink = null;
        private int val;
        private boolean isFirst;
        BinaryTreeNode(int val){
            this.val = val;
        }
    }
    void initTree(){
        root = new BinaryTreeNode(10);
        root.llink = new BinaryTreeNode(6);
        root.rlink = new BinaryTreeNode(14);
        root.llink.llink = new BinaryTreeNode(4);
        root.llink.rlink = new BinaryTreeNode(8);
        root.rlink.llink = new BinaryTreeNode(12);
        root.rlink.rlink = new BinaryTreeNode(16);

    }
    public BinaryTreeNode getRoot(){
        return root;
    }

    //前序遍历--递归
    ArrayList preOrder(BinaryTreeNode cur,ArrayList<Integer> list){
        if (cur!=null){
            list.add(cur.val);
            preOrder(cur.llink,list);
            preOrder(cur.rlink,list);
        }
        return list;
    }
    //前序遍历--非递归
    ArrayList preOrder2(BinaryTreeNode cur,ArrayList<Integer> list){
        LinkedList<BinaryTreeNode> stack = new LinkedList<>();
        while (cur!=null || !stack.isEmpty()){
            if (cur != null){
                list.add(cur.val);
                stack.push(cur);//push 在队首添加元素,add在队尾添加元素
                cur = cur.llink;
            } else{
                BinaryTreeNode node = stack.pop();//pop在队首提取元素
                cur = node.rlink;
            }
        }
        return list;
    }
    //中遍历--递归
    ArrayList inOrder(BinaryTreeNode cur,ArrayList<Integer> list){
        if(cur != null){
            inOrder(cur.llink,list);
            list.add(cur.val);
            inOrder(cur.rlink,list);
        }
        return list;
    }

    //中遍历--递归
    ArrayList inOrder2(BinaryTreeNode cur,ArrayList<Integer> list){
        LinkedList<BinaryTreeNode> stack = new LinkedList<>();
        while (cur != null || !stack.isEmpty()){
            if(cur!=null){
                stack.push(cur);
                cur = cur.llink;
            }else{
                list.add(cur.val);
                BinaryTreeNode node = stack.pop();//pop在队首提取元素
                cur = node.rlink;
            }
        }
        return list;
    }

    //后续遍历--递归
    ArrayList postOrder(BinaryTreeNode cur,ArrayList<Integer> list){
        if (cur!=null){
            postOrder(cur.llink,list);
            postOrder(cur.rlink,list);
            list.add(cur.val);
        }
        return list;
    }
    //后续遍历--递归
    ArrayList postOrder2(BinaryTreeNode cur,ArrayList<Integer> list){
        if(cur == null){
            return list;
        }
        LinkedList<BinaryTreeNode> stack = new LinkedList<>();
        BinaryTreeNode last = null;////上次访问的结点

        //把cur移到左子树的最下边
        while (cur!=null){
            stack.push(cur);
            cur = cur.llink;
        }
        while(!stack.isEmpty()){
            cur = stack.pop();
            //一个根节点被访问的前提是:无右子树或右子树已被访问过
            if (cur.rlink!=null&&cur.rlink!=last){
                stack.push(cur);//根节点再次入栈
                cur = cur.rlink;//进入右子树,且可肯定右子树一定不为空
                while(cur!=null){
                    //再走到右子树的最左边
                    stack.push(cur);
                    cur = cur.llink;
                }
            }else{
                //访问
                list.add(cur.val);
                //修改最近被访问的节点
                last = cur;
            }
        }

        return list;
    }

}

二叉树有很多特例,

  • 二叉搜索树:左节点总是小于或等于根节点,而右节点总是大于或等于根节点。
  • 堆:堆分为最大堆和最小堆
  • 红黑树:把树的节点定义成红、黑两种颜色,并确保根节点到叶节点的最长距离的长度不超过最短路径的两倍。

1.1.2. 二叉搜索树

它是一种特殊的二叉树,改善了二叉树查找效率。

  • 左节点总是小于或等于根节点。
  • 右节点总是大于或等于根节点。

1.1.3. 平衡二叉树AVL

1.1.4. 红黑树

1.1.5. B树:B+、B-


1.2. 剑指Offer

1.2.1. 重建二叉树

题目中给出二叉树前序遍历和中序遍历的数据,让我们得到二叉树的结构,我们可以根据二叉树遍历特性重建二叉树。

  • 前序:根-左-右。因此可以确定,当前树的根结点。
  • 中序:左-根-右。根据前序遍历得到的根节点,可以将当前这个树分成两个树,根节点左边的都是左子树,右边的都是右子树。

import java.util.Arrays;

public class Solution {
    public TreeNode reConstructBinaryTree(int [] pre,int [] in) {
        if (pre.length==0||in.length==0){
            return null;
        }
        //此树的根
        TreeNode root=new TreeNode(pre[0]);
        for (int i = 0; i < in.length; i++) {
            if(root.val==in[i]){
                //左子树
                root.left = reConstructBinaryTree(Arrays.copyOfRange(pre, 1, i + 1),Arrays.copyOfRange(in, 0, i));
                //右子树
                root.right = reConstructBinaryTree(Arrays.copyOfRange(pre, i + 1, pre.length),Arrays.copyOfRange(in, i + 1, in.length));
            }
        }

        return root;
    }

}

1.2.2. 二叉树的下一个节点

package wang.windranger.M8;

public class Solution {
    public TreeLinkNode GetNext(TreeLinkNode pNode) {
        if (pNode == null) {
            return null;
        } else if (pNode.right != null) {//1.有右子树,右子树最左的节点:b>h; e>I; a>f; c>g
            TreeLinkNode rNode = pNode.right;
            //找到最左节点
            while (rNode.left != null) {
                rNode = rNode.left;
            }
            return rNode;
        } else if (pNode.next != null && pNode.next.left == pNode) {
            return pNode.next;
        } else if (pNode.next != null) {
            TreeLinkNode fNode = pNode.next;
            while (fNode.next != null && fNode.next.right == fNode) {
                fNode = fNode.next;
            }
            return fNode.next;
        }
        return null;
    }

    public TreeLinkNode genTree() {
        TreeLinkNode a = new TreeLinkNode('a');
        TreeLinkNode b = new TreeLinkNode('b');
        TreeLinkNode c = new TreeLinkNode('c');
        TreeLinkNode d = new TreeLinkNode('d');
        TreeLinkNode e = new TreeLinkNode('e');
        TreeLinkNode f = new TreeLinkNode('f');
        TreeLinkNode g = new TreeLinkNode('g');
        TreeLinkNode h = new TreeLinkNode('h');
        TreeLinkNode i = new TreeLinkNode('i');
        a.left = b;
        a.right = c;
        b.left = d;
        b.right = e;
        b.next = a;
        c.left = f;
        c.right = g;
        c.next = a;
        d.next = b;
        e.left = h;
        e.right = i;
        e.next = b;
        f.next = c;
        g.next = c;
        h.next = e;
        i.next = e;
        return g;
    }
}

1.3. LeetCode

1.3.1. 94. 二叉树的中序遍历

public List<Integer> inorderTraversal(TreeNode root) {
    List<Integer> list = new ArrayList<>();
    inOrder(root, list);
    return list;
}

public void inOrder(TreeNode node, List<Integer> list) {
    if (node != null) {
        inOrder(node.left,list);
        list.add(node.val);
        inOrder(node.right,list);
    }
}

1.3.2. 144. 二叉树的前序遍历

public List<Integer> preorderTraversal(TreeNode root) {
    List<Integer> list = new ArrayList<>();
    preorder(root, list);
    return list;
}

public void preorder(TreeNode node, List<Integer> list) {
    if (node != null) {
        list.add(node.val);
        preorder(node.left,list);
        preorder(node.right,list);
    }
}

1.3.3. 145. 二叉树的后序遍历

public List<Integer> postorderTraversal(TreeNode root) {
    List<Integer> list = new ArrayList<>();
    postorder(root, list);
    return list;
}

public void postorder(TreeNode node, List<Integer> list) {
    if (node != null) {
        postorder(node.left, list);
        postorder(node.right, list);
        list.add(node.val);
    }
}

1.3.4. 590. N叉树的后序遍历

public List<Integer> postorder(Node root) {
    List<Integer> list = new ArrayList<>();
    postorder(root,list);
    return list;
}
public void postorder(Node node,List<Integer> list){
    if (node!=null){
        if (node.children!=null){
            node.children.forEach(item->{
                postorder(item,list);
            });
        }
        list.add(node.val);
    }
}

1.3.5. 589. N叉树的前序遍历

public List<Integer> preorder(Node root) {
    List<Integer> list = new ArrayList<>();
    preorder(root,list);
    return list;
}
public void preorder(Node node,List<Integer> list){
    if (node!=null){
        list.add(node.val);
        if (node.children!=null){
            node.children.forEach(item->{
                preorder(item,list);
            });
        }
    }
}

1.3.6. 429. N叉树的层序遍历

// 使用队列存储
public List<List<Integer>> levelOrder(Node root) {
    if (root==null){
        return new ArrayList<>();
    }
    List<List<Integer>> ans = new ArrayList<>();
    Queue<Node> queue = new LinkedList<>();
    queue.add(root);
    while (queue.size()!=0){
        levelOrder(queue, ans);
    }
    return ans;
}
// 遍历一层
public void levelOrder(Queue<Node> queue, List<List<Integer>> ans) {
    List<Integer> list = new ArrayList<>();
    for (int i = 0; i < queue.size(); i++) {
        Node node = queue.remove();
        list.add(node.val);
        if (node.children != null) {
            queue.addAll(node.children);
        }
    }
    ans.add(list);
}

1.4. 递归

  1. 初始条件
  2. 执行语句
  3. 回调函数
  4. 清除状态

1.4.1. 70. 爬楼梯

public int climbStairs(int n) {
    // 初始化条件
    if (n == 1) {
        return 1;
    } else if (n == 2) {
        return 2;
    }
    // 执行条件
    return climbStairs(n - 1) + climbStairs(n - 2);
}

1.4.2. 226. 翻转二叉树

public TreeNode invertTree(TreeNode root) {
    if (root != null) {
        // 反转自己的两边
        TreeNode temp = root.left;
        root.left = root.right;
        root.right = temp;
        // 递归左侧和右侧
        invertTree(root.left);
        invertTree(root.right);
    }
    return root;
}

1.4.3. 98. 验证二叉搜索树

中序遍历后,如果是二叉搜索树,则是按顺序排列的。

public boolean isValidBST(TreeNode root) {
    if (root==null){
        return true;
    }
    List<Integer> list = new ArrayList<>();
    order(root, list);
    int min = list.get(0);
    for (int i = 1; i < list.size(); i++) {
        if (min < list.get(i)) {
            min = list.get(i);
        } else {
            return false;
        }
    }
    return true;
}
// 中序遍历
public List<Integer> order(TreeNode node, List<Integer> list) {
    if (node != null) {
        order(node.left, list);
        list.add(node.val);
        order(node.right, list);
    }
    return list;
}

1.4.4. 104. 二叉树的最大深度

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

1.4.5. 111. 二叉树的最小深度

二叉树的最小深度-理解递归结束条件这个写的不错

public int minDepth(TreeNode root) {
    if (root == null) {
        return 0;
    } else if (root.right == null && root.left == null) {
        return 1;
    } else {
        int left = minDepth(root.left);
        int right = minDepth(root.right);
        if (root.left == null || root.right == null) {
            // 说明肯定有一边是没有 节点的。不符合题意
            return left + right + 1;
        }else{
            return Math.min(left, right) + 1;
        }
    }
}
// 简化
    public int minDepth(TreeNode root) {
        if (root == null) {
            return 0;
        }
        int left = minDepth(root.left);
        int right = minDepth(root.right);
        //1.如果左孩子和右孩子有为空的情况,直接返回m1+m2+1
        //2.如果都不为空,返回较小深度+1
        return root.left == null || root.right == null ? left + right + 1 : Math.min(left, right) + 1;
    }

1.4.6. 236. 二叉树的最近公共祖先

这个写的不错。官方递归答案题解(易懂)

以要找的节点分别为p和q为例:首先分析公共祖先一共可以分为以下三种情况:

  • 如果一个节点的左右都能达到终点,那么当前节点一定是公共祖先。
  • 如果当前节点左树可以找到一个值,当前节点值等于另一个值,那么祖先也就是当前值。
  • 如果当前节点右树可以找到一个值,当前节点值等于另一个值,那么祖先也一定就是当前值。
  • 这三种情况用代码表示就是:
    • left=1,right=1,mid=0
    • left=1,right=0,mid=1
    • left=0,right=1,mid=1
    • left表示向左子树递归是否能找到通向p/q,能找到赋值1,不能的话赋值0
    • right表示向右子树递归是否能找到通向p/q,能找到赋值1,不能的话赋值0
    • mid表示当前节点是否等于p/q,等于的话赋值1,不等于赋值。
TreeNode ans = null;
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
    find(root, p, q);
    return ans;
}

boolean find(TreeNode root, TreeNode p, TreeNode q) {
    if (root == null) {
        return false;
    }
    int left = find(root.left, p, q) ? 1 : 0;
    int right = find(root.right, p, q) ? 1 : 0;
    int mid = (root == p || root == q) ? 1 : 0;
    if (left + right + mid == 2) {
        ans = root;
    }
    return (left + right + mid) > 0;
}

1.4.7. 105. 从前序与中序遍历序列构造二叉树

剑指offer原题。

public TreeNode buildTree(int[] preorder, int[] inorder) {
    if (preorder.length == 0 || inorder.length == 0) {
        return null;
    }
    TreeNode root = new TreeNode(preorder[0]);
    for (int i = 0; i < inorder.length; i++) {
        if (inorder[i] == root.val) {
            root.left = buildTree(Arrays.copyOfRange(preorder, 1, i + 1), Arrays.copyOfRange(inorder, 0, i));
            root.right = buildTree(Arrays.copyOfRange(preorder, i + 1, inorder.length), Arrays.copyOfRange(inorder, i + 1, inorder.length));
        }
    }
    return root;
}

1.5. 回溯

参考回溯算法详解

List<List<Integer>> res = new LinkedList<>(); // 总结果列表
int main(int[] nums){
    LinkedList<Integer> track = new LinkedList<>() // 每次结果的列表
    backtrack(nums,track);
    return res;
}
void backtrack(int[] nums, LinkedList<Integer> track) {
    // 如果满足约束条件,添加该路径
    if (...) { 
        res.add(路径);
        // 如果 条件是 固定长度,使用return;不固定长度,去掉return。
        return; 
    }
    for 选择 in 选择列表:
        // 做选择
        路径.add(选择)
        // 回溯
        backtrack(路径, 选择列表)
        // 撤销选择
        路径.remove(选择)
}

1.5.1. 22. 括号生成

public List<String> generateParenthesis(int n) {
    List<String> ans = new ArrayList<>();
    backtrack(ans, "", 0, 0, n);
    return ans;
}

public void backtrack(List<String> ans, String cur, int open, int close, int max) {
    if (cur.length() == max * 2) {
        ans.add(cur);
        return;
    }
    if (open < max) {
        backtrack(ans, cur + "(", open + 1, close, max);
    }
    if (close < open) {
        backtrack(ans, cur + ")", open, close + 1, max);
    }
}

1.5.2. 77. 组合

List<List<Integer>> res = new LinkedList<>();

public List<List<Integer>> combine(int n, int k) {
    LinkedList<Integer> track = new LinkedList<>();
    if (k != 0) {
        backtrack(1, n, k, track);
    }
    return res;
}

private void backtrack(int i, int n, int k, LinkedList<Integer> track) {
    if (track.size() == k) {
        res.add(new LinkedList<>(track));
        return;
    }
    for (int j = i; j <= n; j++) {
        // 做选择
        track.add(j);
        backtrack(j + 1, n, k, track);
        track.removeLast();
    }
}

1.5.3. 46. 全排列

List<List<Integer>> res = new LinkedList<>();
public List<List<Integer>> permute(int[] nums) {
    // 记录「路径」
    LinkedList<Integer> track = new LinkedList<>();
    // nums 选择列表, track路径
    backtrack(nums, track);
    return res;
}
private void backtrack(int[] nums, LinkedList<Integer> track) {
    if (track.size() == nums.length) {
        // 终止:添加一条选择路径
        res.add((List<Integer>) track.clone());
        return;
    }
    for (int num : nums) {
        if (track.contains(num)) {
            continue;
        }
        track.add(num);
        backtrack(nums, track);
        track.removeLast();
    }
}

1.5.4. 47. 全排列 II

Set<List<Integer>> res = new HashSet<>();

public List<List<Integer>> permuteUnique(int[] nums) {
    LinkedList<Integer> track = new LinkedList<>();
    backtrack(new LinkedList<>(), nums, track);
    return new LinkedList<>(res);
}

private void backtrack(LinkedList<Integer> selected, int[] nums, LinkedList<Integer> track) {
    if (track.size() == nums.length) {
        res.add(new LinkedList<>(track));
        return;
    }
    for (int i = 0; i < nums.length; i++) {
        if (selected.contains(i)) {
            continue;
        }
        // 做选择
        track.add(nums[i]);
        selected.add(i);
        // 回溯
        backtrack(selected, nums, track);
        // 清楚选择
        track.removeLast();
        selected.removeLast();
    }
}

1.5.5. 50. Pow(x, n)

一直overFlow

public double myPow(double x, int n) {
    if (n == 0) {
        return 1;
    }
    if (n < 0) {
        return myPow(1 / x, -n);
    }

    return n % 2 == 1 ? x * myPow(x, n - 1) : myPow(x * x, n / 2);
}

1.5.6. 78. 子集

List<List<Integer>> res = new LinkedList<>();
public List<List<Integer>> subsets(int[] nums) {
    LinkedList<Integer> track = new LinkedList<>();
    backtrack(nums, 0, track);
    return res;
}
private void backtrack(int[] nums, int start, LinkedList<Integer> track) {
    res.add(new LinkedList<>(track));

    // 注意 i 从 start 开始递增
    for (int i = start; i < nums.length; i++) {
        // 做选择
        track.add(nums[i]);
        // 回溯
        backtrack(nums, i + 1, track);
        // 撤销选择
        track.removeLast();
    }
}

1.5.7. 169. 多数元素

不是回溯。

public int majorityElement(int[] nums) {
    Map<Integer, Integer> map = new HashMap<>();
    for (int num : nums) {
        if (map.containsKey(num)) {
            map.put(num, map.get(num) + 1);
        } else {
            map.put(num, 1);
        }
    }
    final int[] max = {0};
    final int[] index = {0};
    map.forEach((key, value) -> {
        if (value > max[0]) {
            index[0] = key;
            max[0] = value;
        }
    });
    return index[0];
}

1.5.8. 17. 电话号码的字母组合

private String[] letterMap = {
        "",     //0
        "",     //1
        "abc",  //2
        "def",  //3
        "ghi",  //4
        "jkl",  //5
        "mno",  //6
        "pqrs", //7
        "tuv",  //8
        "wxyz"  //9
};

List<String> res = new LinkedList<>();

public List<String> letterCombinations(String digits) {
    StringBuilder track = new StringBuilder();
    if (!"".equals(digits)) {
        backtrack(0, digits, track);
    }
    return res;
}

private void backtrack(int i, String nums, StringBuilder track) {
    if (track.length() == nums.length()) {
        res.add(track.toString());
        return;
    }
    // 取出第i个元素
    char digit = nums.charAt(i);
    String digits = this.letterMap[digit - '0'];
    for (int j = 0; j < digits.length(); j++) {
        // 做选择
        track.append(digits.charAt(j));
        // 回溯
        backtrack(i + 1, nums, track);
        // 撤销选择
        track.deleteCharAt(track.length() - 1);
    }
}

1.5.9. 51. N皇后

List<List<String>> res = new LinkedList<>();

public List<List<String>> solveNQueens(int n) {
    ArrayList<String> track = new ArrayList<>();
    StringBuilder str = new StringBuilder();
    for (int i = 0; i < n; i++) {
        str.append('.');
    }
    for (int i = 0; i < n; i++) {
        track.add(str.toString());
    }
    backtrack(0, track);
    return res;
}

private void backtrack(int row, ArrayList<String> track) {
    if (row == track.size()) {
        res.add(new LinkedList<>(track));
        return;
    }
    for (int col = 0; col < track.size(); col++) {
        if (isConflict(row, col, track)) {
            continue;
        }
        StringBuilder rows = new StringBuilder(track.get(row));
        rows.setCharAt(col, 'Q');
        track.set(row, rows.toString());
        backtrack(row + 1, track);
        rows.setCharAt(col, '.');
        track.set(row, rows.toString());
    }
}

/* 是否可以在 board[row][col] 放置皇后? */
private boolean isConflict(int row, int col, ArrayList<String> track) {
    int n = track.size();
    // 检查列是否有皇后互相冲突
    for (String s : track) {
        if (s.charAt(col) == 'Q') {
            return true;
        }
    }
    // 检查右上方是否有皇后互相冲突
    for (int i = row - 1, j = col + 1; i >= 0 && j < n; i--, j++) {
        if (track.get(i).charAt(j) == 'Q') {
            return true;
        }
    }
    // 检查左上方是否有皇后互相冲突
    for (int i = row - 1, j = col - 1; i >= 0 && j >= 0; i--, j--) {
        if (track.get(i).charAt(j) == 'Q') {
            return true;
        }
    }
    return false;
}

1.6. DFS、BFS

1.6.1. 102. 二叉树的层次遍历

public List<List<Integer>> levelOrder(TreeNode root) {
    Deque<TreeNode> deque = new LinkedList<>();
    List<List<Integer>> res = new LinkedList<>();
    if (root == null) {
        return res;
    }
    // 添加 root
    deque.add(root);
    int layer = 0;
    while (!deque.isEmpty()) {
        // 添加 新的一层的list
        res.add(new LinkedList<>());
        // 记录长度
        int layerLength = deque.size();
        for (int i = 0; i < layerLength; i++) {
            TreeNode node = deque.remove();
            res.get(layer).add(node.val);
            if (node.left != null) {
                deque.add(node.left);
            }
            if (node.right != null) {
                deque.add(node.right);
            }
        }
        layer++;// 层数增加
    }
    return res;
}

1.6.2. 515. 在每个树行中找最大值

public List<Integer> largestValues(TreeNode root) {
    Deque<TreeNode> deque = new LinkedList<>();
    List<Integer> res = new LinkedList<>();
    if (root == null) {
        return res;
    }
    deque.add(root);
    while (!deque.isEmpty()) {
        int length = deque.size();
        int max = Integer.MIN_VALUE;
        for (int i = 0; i < length; i++) {
            TreeNode node = deque.remove();
            max = Math.max(max, node.val);
            if (node.left != null) {
                deque.add(node.left);
            }
            if (node.right != null) {
                deque.add(node.right);
            }
        }
        res.add(max);
    }
    return res;
}

1.6.3. 127. 单词接龙

public int ladderLength(String beginWord, String endWord, List<String> wordList) {
    Set<String> dict = new HashSet<>(wordList);
    if (!dict.contains(endWord)) {
        return 0;
    }
    int step = 0;
    Deque<String> deque = new LinkedList<>();
    deque.add(beginWord);
    while (!deque.isEmpty()) {
        step++;
        int length = deque.size();
        for (int i = 0; i < length; i++) {
            char[] arrays = deque.remove().toCharArray();
            for (int j = 0; j < arrays.length; j++) {
                char origin = arrays[j];
                for (char c = 'a'; c <= 'z'; ++c) {
                    if (c != origin) {
                        arrays[j] = c;
                        String t = new String(arrays);
                        if (endWord.equals(t)) {
                            return step + 1;
                        } else if (dict.contains(t)) {
                            dict.remove(t);
                            deque.add(t);
                        }
                    }
                }
                arrays[j] = origin;
            }
        }
    }
    return 0;
}

1.6.4. 200. 岛屿数量

1.6.5. 529. 扫雷游戏

1.6.6. 297. 二叉树的序列化与反序列化

实际上考DFS和BFS

广搜

public String serialize(TreeNode root) {
    Deque<TreeNode> deque = new LinkedList<>();
    StringBuilder result = new StringBuilder();
    deque.add(root);
    while (deque.size() != 0) {
        TreeNode node = deque.remove();
        if (node != null) {
            deque.add(node.left);
            deque.add(node.right);
            result.append(node.val).append(",");
        } else {
            result.append("null").append(",");
        }
    }
    return result.toString();
}

// Decodes your encoded data to tree.
public TreeNode deserialize(String data) {
    String[] arrays = data.split(",");
    if ("null".equals(arrays[0])) {
        return null;
    } else {
        TreeNode root = new TreeNode(Integer.parseInt(arrays[0]));
        Deque<TreeNode> deque = new LinkedList<>();
        deque.add(root);
        int i = 1;
        while (deque.size() != 0) {
            TreeNode node = deque.remove();
            if (node != null) {
                String left = arrays[i++];
                node.left = "null".equals(left) ? null : new TreeNode(Integer.parseInt(left));
                deque.add(node.left);
                String right = arrays[i++];
                node.right = "null".equals(right) ? null : new TreeNode(Integer.parseInt(right));
                deque.add(node.right);
            }
        }
        return root;
    }
}

深搜

public String serialize(TreeNode root) {
    StringBuilder str = new StringBuilder();
    if(root==null){
        return null;
    }
    order(root, str);
    return str.toString();
}

public void order(TreeNode node, StringBuilder stringBuilder) {
    if (node != null) {
        stringBuilder.append(node.val).append(",");
        order(node.left, stringBuilder);
        order(node.right, stringBuilder);
    } else {
        stringBuilder.append("null").append(",");
    }
}

public TreeNode deserialize(String data) {
    List<String> list = new LinkedList<String>(Arrays.asList(data.split(",")));
    return rdeserialize(list);
}

private TreeNode rdeserialize(List<String> list) {
    if (list.get(0) == null) {
        list.remove(0);
        return null;
    }
    TreeNode node = new TreeNode(Integer.parseInt(list.get(0)));
    list.remove(0);
    node.left = rdeserialize(list);
    node.right = rdeserialize(list);
    return node;
}

1.6.7. 695. 岛屿的最大面积

深搜

public int maxAreaOfIsland(int[][] grid) {
    int len = grid.length;
    int width = grid[0].length;
    int max = 0;
    Set<String> discard = new HashSet<>();
    for (int i = 0; i < len; i++) {
        for (int j = 0; j < width; j++) {
            if (grid[i][j] == 1 && !discard.contains(i + "," + j)) {
                Set<String> track = new HashSet<>();
                track.add(i + "," + j);
                order(track, grid, i, j, len, width);
                discard.addAll(track);
                max = Math.max(track.size(), max);
            }
        }
    }
    return max;
}

public void order(Set<String> track, int[][] grid, int i, int j, int len, int width) {
    if (!track.contains((i + 1) + "," + j) && i + 1 < len && grid[i + 1][j] == 1) {
        track.add((i + 1 )+ "," + j);
        order(track, grid, i + 1, j, len, width);
    }
    if (!track.contains((i - 1) + "," + j) && i - 1 >= 0 && grid[i - 1][j] == 1) {
        track.add((i - 1) + "," + j);
        order(track, grid, i - 1, j, len, width);
    }
    if (!track.contains(i + "," + (j + 1)) && j + 1 < width && grid[i][j + 1] == 1) {
        track.add(i + "," + (j + 1));
        order(track, grid, i, j + 1, len, width);
    }
    if (!track.contains(i + "," + (j - 1)) && j - 1 >= 0 && grid[i][j - 1] == 1) {
        track.add(i + "," + (j - 1));
        order(track, grid, i, j - 1, len, width);
    }
}

results matching ""

    No results matching ""