树

二叉树基础

树节点定义

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

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

二叉树遍历

前序遍历（LeetCode 144）

答案：

// 递归
public List<Integer> preorderTraversal(TreeNode root) {
    List<Integer> result = new ArrayList<>();
    preorder(root, result);
    return result;
}

private void preorder(TreeNode node, List<Integer> result) {
    if (node == null) return;
    result.add(node.val);
    preorder(node.left, result);
    preorder(node.right, result);
}

// 迭代
public List<Integer> preorderTraversal(TreeNode root) {
    List<Integer> result = new ArrayList<>();
    if (root == null) return result;

    Stack<TreeNode> stack = new Stack<>();
    stack.push(root);

    while (!stack.isEmpty()) {
        TreeNode node = stack.pop();
        result.add(node.val);

        if (node.right != null) stack.push(node.right);
        if (node.left != null) stack.push(node.left);
    }
    return result;
}

中序遍历（LeetCode 94）

public List<Integer> inorderTraversal(TreeNode root) {
    List<Integer> result = new ArrayList<>();
    Stack<TreeNode> stack = new Stack<>();
    TreeNode curr = root;

    while (curr != null || !stack.isEmpty()) {
        while (curr != null) {
            stack.push(curr);
            curr = curr.left;
        }
        curr = stack.pop();
        result.add(curr.val);
        curr = curr.right;
    }
    return result;
}

层序遍历（LeetCode 102）

public List<List<Integer>> levelOrder(TreeNode root) {
    List<List<Integer>> result = new ArrayList<>();
    if (root == null) return result;

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

    while (!queue.isEmpty()) {
        int size = queue.size();
        List<Integer> level = new ArrayList<>();

        for (int i = 0; i < size; i++) {
            TreeNode node = queue.poll();
            level.add(node.val);

            if (node.left != null) queue.offer(n.left);
            if (node.right != null) queue.offer(node.right);
        }
        result.add(level);
    }
    return result;
}

二叉树经典题目

二叉树的最大深度（LeetCode 104）

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

翻转二叉树（LeetCode 226）

public TreeNode invertTree(TreeNode root) {
    if (root == null) return null;

    TreeNode temp = root.left;
    root.left = invertTree(root.right);
    root.right = invertTree(temp);

    return root;
}

对称二叉树（LeetCode 101）

public boolean isSymmetric(TreeNode root) {
    return isMirror(root, root);
}

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

二叉树的直径（LeetCode 543）

private int maxDiameter = 0;

public int diameterOfBinaryTree(TreeNode root) {
    depth(root);
    return maxDiameter;
}

private int depth(TreeNode node) {
    if (node == null) return 0;

    int left = depth(node.left);
    int right = depth(node.right);

    maxDiameter = Math.max(maxDiameter, left + right);

    return Math.max(left, right) + 1;
}

二叉树的最近公共祖先（LeetCode 236）

public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
    if (root == null || root == p || root == q) {
        return root;
    }

    TreeNode left = lowestCommonAncestor(root.left, p, q);
    TreeNode right = lowestCommonAncestor(root.right, p, q);

    if (left != null && right != null) {
        return root;
    }
    return left != null ? left : right;
}

二叉搜索树

验证二叉搜索树（LeetCode 98）

public boolean isValidBST(TreeNode root) {
    return isValid(root, null, null);
}

private boolean isValid(TreeNode node, Integer min, Integer max) {
    if (node == null) return true;

    if ((min != null && node.val <= min) || (max != null && node.val >= max)) {
        return false;
    }

    return isValid(node.left, min, node.val) && isValid(node.right, node.val, max);
}

二叉搜索树中第K小的元素（LeetCode 230）

private int count = 0;
private int result = 0;

public int kthSmallest(TreeNode root, int k) {
    inorder(root, k);
    return result;
}

private void inorder(TreeNode node, int k) {
    if (node == null) return;

    inorder(node.left, k);

    count++;
    if (count == k) {
        result = node.val;
        return;
    }

    inorder(node.right, k);
}

练习题

1. 路径总和（LeetCode 112）
2. 从前序与中序遍历序列构造二叉树（LeetCode 105）
3. 二叉树的右视图（LeetCode 199）
4. 完全二叉树的节点个数（LeetCode 222）
5. 二叉树的序列化与反序列化（LeetCode 297）