Skip to main content

二叉树

class TreeNode {
    public TreeNode left, right;
    public int val;

    public TreeNode(int val) {
        this.val = val;
    }
}

顺序遍历​

先序遍历: 根->左->右 中序遍历: 左->根->右 后序遍历: 左->右->根

// 先序遍历
public void preTraverse(TreeNode root) {
    if (root != null) {
        System.out.println(root.val);
        preTraverse(root.left);
        preTraverse(root.right);
    }
}

// 中序遍历
public void inTraverse(TreeNode root) {
    if (root != null) {
        inTraverse(root.left);
        System.out.println(root.val);
        inTraverse(root.right);
    }
}

// 后序遍历
public void postTraverse(TreeNode root) {
    if (root != null) {
        postTraverse(root.left);
        postTraverse(root.right);
        System.out.println(root.val);
    }
}

层次遍历​

// 层次遍历(DFS)
public static List<List<Integer>> levelOrder(TreeNode root) {
    List<List<Integer>> res = new ArrayList<>();
    if (root == null) {
        return res;
    }
    
    dfs(root, res, 0);
    return res;
}

private void dfs(TreeNode root, List<List<Integer>> res, int level) {
    if (root == null) {
        return;
    }
    if (level == res.size()) {
        res.add(new ArrayList<>());
    }
    res.get(level).add(root.val);
    
    dfs(root.left, res, level + 1);
    dfs(root.right, res, level + 1);
}

// 层次遍历(BFS)
public List<List<Integer>> levelOrder(TreeNode root) {
    List result = new ArrayList();

    if (root == null) {
        return result;
    }

    Queue<TreeNode> queue = new LinkedList<TreeNode>();
    queue.offer(root);

    while (!queue.isEmpty()) {
        ArrayList<Integer> level = new ArrayList<Integer>();
        int size = queue.size();
        for (int i = 0; i < size; i++) {
            TreeNode head = queue.poll();
            level.add(head.val);
            if (head.left != null) {
                queue.offer(head.left);
            }
            if (head.right != null) {
                queue.offer(head.right);
            }
        }
        result.add(level);
    }

    return result;
}

// "Z"字遍历
public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
    List<List<Integer>> result = new ArrayList<>();
    
    if (root == null){
        return result;
    }
    
    Queue<TreeNode> queue = new LinkedList<>();
    queue.offer(root);
    boolean isFromLeft = false;
    while(!queue.isEmpty()){
        int size = queue.size();
        isFromLeft = !isFromLeft;
        List<Integer> list = new ArrayList<>();
        for(int i = 0; i < size; i++){
            TreeNode node;
            if (isFromLeft){
                node = queue.pollFirst();
            }else{
                node = queue.pollLast();
            }
            list.add(node.val);
            
            if (isFromLeft){
                if (node.left != null){
                    queue.offerLast(node.left);
                }
                if (node.right != null){
                    queue.offerLast(node.right);
                }
            }else{
                if (node.right != null){
                    queue.offerFirst(node.right);
                }
                if (node.left != null){
                    queue.offerFirst(node.left);
                }
            }
        }
        result.add(list);
    }
    
    return result;
}

左右翻转​

public void invert(TreeNode root) {
    if (root == null) {
        return;
    }
    TreeNode temp = root.left;
    root.left = root.right;
    root.right = temp;
    
    invert(root.left);
    invert(root.right);
}

最大值​

public int getMax(TreeNode root) {
    if (root == null) {
        return Integer.MIN_VALUE;
    } else {
        int left = getMax(root.left);
        int right = getMax(root.right);
        return Math.max(Math.max(left, rigth), root.val);
    }
}

最大深度​

public int maxDepth(TreeNode root) {
    if (root == null) {
        return 0;
    }

    int left = maxDepth(root.left);
    int right = maxDepth(root.right);
    return Math.max(left, right) + 1;
}

最小深度​

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

平衡二叉树​

平衡二叉树每一个节点的左右两个子树的高度差不超过1

public boolean isBalanced(TreeNode root) {
    return maxDepth(root) != -1;
}

private int maxDepth(TreeNode root) {
    if (root == null) {
        return 0;
    }

    int left = maxDepth(root.left);
    int right = maxDepth(root.right);
    if (left == -1 || right == -1 || Math.abs(left - right) > 1) {
        return -1;
    }
    return Math.max(left, right) + 1;
}

二叉搜索树

验证二叉搜索树​

public boolean isValidBST(TreeNode root) {
    return isValidBST(root, Long.MIN_VALUE, Long.MAX_VALUE);
}

private boolean isValidBST(TreeNode root, long min, long max){
    if (root == null) {
        return true;
    }
    
    if (root.val <= min || root.val >= max){
        return false;
    }
    
    return isValidBST(root.left, min, root.val) && isValidBST(root.right, root.val, max);
}

第K小的元素​

增加getCount方法来获取传入节点的子节点数（包括自己），从root节点开始判断k值和子节点数的大小决定递归路径是往左还是往右。

public int kthSmallest(TreeNode root, int k) {
    if (root == null) {
        return 0;
    }
    
    int leftCount = getCount(root.left);
    if (leftCount >= k) {
        return kthSmallest(root.left, k);
    } else if (leftCount + 1 == k) {
        return root.val;
    } else {
        return kthSmallest(root.right, k - leftCount - 1);
    }
}

private int getCount(TreeNode root) {
    if (root == null) {
        return 0;
    }
    
    return getCount(root.left) + getCount(root.right) + 1;
}

数组 / 双指针

加一​

给定一个非负数，表示一个数字数组，在该数的基础上+1，返回一个新的数组。该数字按照数位高低进行排列，最高位的数在列表的最前面。

public int[] plusOne(int[] digits) {
    int carries = 1;
    for(int i = digits.length - 1; i >= 0 && carries > 0; i--){  
        int sum = digits[i] + carries;
        digits[i] = sum % 10;
        carries = sum / 10;
    }
    if(carries == 0) {
        return digits;
    }
        
    int[] rst = new int[digits.length + 1];
    rst[0] = 1;
    for(int i = 1; i < rst.length; i++){
        rst[i] = digits[i - 1];
    }
    return rst;
}

删除元素​

给定一个数组和一个值，在原地删除与值相同的数字，返回新数组的长度。

public int removeElement(int[] A, int elem) {
    if (A == null || A.length == 0) {
        return 0;
    }
    
    int index = 0;
    for (int i = 0; i < A.length; i++) {
        if (A[i] != elem) {
            A[index++] = A[i];
        } 
    }
    
    return index;
}

删除排序数组中的重复数字​

在原数组中“删除”重复出现的数字，使得每个元素只出现一次，并且返回“新”数组的长度。

public int removeDuplicates(int[] A) {
    if (A == null || A.length == 0) {
        return 0;
    }
    
    int size = 0;
    for (int i = 0; i < A.length; i++) {
        if (A[i] != A[size]) {
            A[++size] = A[i];
        }
    }
    return size + 1;
}