二叉树

94. 二叉树的中序遍历

java

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

    public void inOrder(TreeNode root, List<Integer> ans) {
        if (root == null) return;
        inOrder(root.left, ans);
        ans.add(root.val);
        inOrder(root.right, ans);
    }
}

104. 二叉树的最大深度

java

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

226. 翻转二叉树

java

// 直接交换节点左右孩子，和官解不同
class Solution {
    public TreeNode invertTree(TreeNode root) {
        if (root == null) {
            return null;
        }
        TreeNode temp = root.left;
        root.left = root.right;
        root.right = temp;
        invertTree(root.left);
        invertTree(root.right);
        return root;
    }
}

101. 对称二叉树

java

class Solution {
    public boolean isSymmetric(TreeNode root) {
        return isSame(root.left, root.right);
    }

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

543. 二叉树的直径

java

// 先按照计算树的高度思路写，左右子树的高度用l, r表示，遍历每个节点的时候更新ans即可
class Solution {
    private int ans;

    public int diameterOfBinaryTree(TreeNode root) {
        height(root);
        return ans;
    }

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

102. 二叉树的层序遍历

java

// 借助队列，BFS
class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> ans = new ArrayList<>();
        if (root == null) return ans;

        Queue<TreeNode> que = new ArrayDeque<>();
        que.offer(root);
        while (!que.isEmpty()) {
            int size = que.size();
            List<Integer> layer = new ArrayList<>(size);
            for (int i = 0; i < size; i++) {
                TreeNode node = que.poll();
                layer.add(node.val);
                if (node.left != null) que.offer(node.left);
                if (node.right != null) que.offer(node.right);
            }
            ans.add(layer);
        }
        return ans;
    }
}

108. 将有序数组转换为二叉搜索树

java

class Solution {
    public TreeNode sortedArrayToBST(int[] nums) {
        return BST(nums, 0, nums.length - 1);
    }

    public TreeNode BST(int[] nums, int left, int right) {
        if (left > right) {
            return null;
        }
        int mid = (left + right) / 2;
        TreeNode root = new TreeNode(nums[mid]);
        root.left = BST(nums, left, mid - 1);
        root.right = BST(nums, mid + 1, right);
        return root;
    }
}

98. 验证二叉搜索树

java

// 作者：灵茶山艾府
// 本质还是中序遍历，如果判断左边，再判断根，最后判断右边
class Solution {
    private long pre = Long.MIN_VALUE;

    public boolean isValidBST(TreeNode root) {
        if (root == null) {
            return true;
        }
        if (!isValidBST(root.left) || pre >= root.val) {
            return false;
        }
        pre = root.val;
        return isValidBST(root.right);
    }
}

230. 二叉搜索树中第K小的元素

java

// 方法一：二叉搜索树中序遍历到第k个节点即可，这里用递归全部遍历了，最佳解还是用栈循环迭代
class Solution {
    private int cnt;
    private int ans;

    public int kthSmallest(TreeNode root, int k) {
        inOrder(root, k);
        return ans;
    }

    public void inOrder(TreeNode root, int k) {
        if (root == null) {
            return;
        }
        inOrder(root.left, k);
        if (++cnt == k) {
            ans = root.val;
        }
        inOrder(root.right, k);
    }
}

// 方法二：利用栈进行迭代，不需要根先入栈，两个while循环一直添加左孩子
class Solution {
    public int kthSmallest(TreeNode root, int k) {
        Deque<TreeNode> stack = new ArrayDeque<>();

        while (root != null || !stack.isEmpty()) {
            while (root != null) {
                stack.push(root);
                root = root.left;
            }
        // 出栈，然后root指向右孩子
            root = stack.pop();
            if (--k == 0) {
                break;
            }
            root = root.right;
        }

        return root.val;
    }
}

199. 二叉树的右视图

java

// 方法一：借助队列进行迭代，每层最后一个即为ans
class Solution {
    public List<Integer> rightSideView(TreeNode root) {
        List<Integer> ans = new ArrayList<>();
        if (root == null) return ans;
        // 栈用Deque, 队列用Queue, 都new ArrayDeque
        Queue<TreeNode> que = new ArrayDeque<>();
        que.offer(root);
        while (!que.isEmpty()) {
            int size = que.size();
            for (int i = 0; i < size; i++) {
                TreeNode node = que.poll();
                if (node.left != null) que.offer(node.left);
                if (node.right != null) que.offer(node.right);
                if (i == size - 1) ans.add(node.val);
            }
        }
        return ans;
    }
}

// 方法二：灵神的递归，根右左的先序遍历，根据往下的深度以及ans的当前size进行填充
class Solution {
    List<Integer> ans = new ArrayList<>();

    public List<Integer> rightSideView(TreeNode root) {
        dfs(root, 0);
        return ans;
    }

    public void dfs(TreeNode root, int depth) {
        if (root == null) return;
        if (depth == ans.size()) {
            ans.add(root.val);
        }
        dfs(root.right, depth + 1);
        dfs(root.left, depth + 1);
    }
}

114. 二叉树展开为链表

java

// 展开为链表就想象成一行，更新next即可

// 方法一：定义一个链表的虚拟头节点，先序遍历
// 需要临时变量temp记录当前节点的右孩子，使得先序遍历正常进行，否则右孩子丢失
public class Solution {
    private TreeNode dummy = new TreeNode();

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

        dummy.right = root;// 此处修改了上一层的节点右指针，会导致原有的右孩子找不到，因此temp先记录，按照先序正常遍历
        dummy = root;
        flatten(root.left);
        flatten(temp);
        root.left = null;
    }
}

// 方法二： 右，左，根，因此建立的链表是从末尾向前
// 作者：一半王二，一半三毛
public class Solution {
    TreeNode tail = null;
    public void flatten(TreeNode root){
        if(root == null) return;
        flatten(root.right);
        flatten(root.left);
        root.left = null;
        root.right = tail;
        tail = root;
    }
}

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

java

// inorder的划分比较好确定，而前序分别可以获取头尾，剩下两个计算即可
class Solution {
    private Map<Integer, Integer> mp = new HashMap<>();

    public TreeNode buildTree(int[] preorder, int[] inorder) {
        for (int i = 0; i < inorder.length; i++) {
            mp.put(inorder[i], i);
        }
        return build(preorder, inorder, 0, preorder.length - 1, 0, inorder.length - 1);
    }

    public TreeNode build(int[] preorder, int[] inorder, int m, int n, int x, int y) {
        if (m > n)
            return null;
        TreeNode root = new TreeNode(preorder[m]);
        int idx = mp.get(preorder[m]);
        root.left = build(preorder, inorder, m + 1, m - x + idx, x, idx - 1);
        root.right = build(preorder, inorder, n + idx + 1 - y, n, idx + 1, y);
        return root;
    }
}

437. 路径总和 III

java

// 哈希，前缀和，深度优先，最后返回父节点回溯
// 注意超出范围，和的部分需要Long，数字后面加L
class Solution {
    private int ans;
    private Map<Long, Integer> map = new HashMap<>();

    public int pathSum(TreeNode root, int targetSum) {
        map.put(0L, 1);
        dfs(root, targetSum, 0L);
        return ans;
    }

    public void dfs(TreeNode root, int targetSum, long curSum) {
        if (root == null) {
            return;
        }
        curSum += root.val;
        ans += map.getOrDefault(curSum - targetSum, 0);
        map.put(curSum, map.getOrDefault(curSum, 0) + 1);

        dfs(root.left, targetSum, curSum);
        dfs(root.right, targetSum, curSum);

        // 返回父节点需要回溯
        if (map.put(curSum, map.get(curSum) - 1) == 1) {
            map.remove(curSum);
        }
    }
}

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

java

// 看灵神，分情况
// 如果p或者q就是根直接返回根
// 否则去左子树找，然后去右子树找，这里是找到其一就有返回值，因此如果左右各在一边结果非空，返回根节点
// 只有一个有返回值
class Solution {
    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) {    // 在左右子数中都有返回结果，说明p, q各在一边
            return root;
        }
        return left != null ? left : right;
    }
}

二叉树 ​

二叉树