算法第十八天|二叉树

周末有事，将后面两天的题提前刷了

530. 二叉搜索树的最小绝对差

 List<Integer> list = new ArrayList<>();

    public int getMinimumDifference(TreeNode root) {
        // 二叉搜索树，求最小差值
        getPreTreeNode(root);
        // 已知节点个数>=2
        // 相邻的两个数相减才会有最小差值

        int minValue = Integer.MAX_VALUE;
        for (int i = 1; i < list.size(); i++) {
            int sub = list.get(i) - list.get(i - 1);
            minValue = Math.min(sub, minValue);
        }

        return minValue;
    }

    private void getPreTreeNode(TreeNode root) {
        if (root == null) {
            return;
        }
        getPreTreeNode(root.left);
        list.add(root.val);
        getPreTreeNode(root.right);
    }

二叉搜索树的中序遍历是一个从小到大的有序数组

既然是有序数组，那么最小值必然是相邻两个元素的差值

501. 二叉搜索树中的众数

    private Map<Integer, Integer> map = new HashMap<>();

    public int[] findMode(TreeNode root) {
        if (root == null) {
            return null;
        }
        getPreTreeNode(root);
        List<Integer> list = new ArrayList<>(map.size());
        int maxSize = 0;
        for (Map.Entry<Integer, Integer> entry : map.entrySet()) {
            maxSize = entry.getValue() > maxSize ? entry.getValue() : maxSize;
        }

        for (Map.Entry<Integer, Integer> entry : map.entrySet()) {
            if (entry.getValue() == maxSize) {
                list.add(entry.getKey());
            }
        }
        return list.stream().mapToInt(i -> i).toArray();
    }

    private void getPreTreeNode(TreeNode root) {
        if (root == null) {
            return;
        }
        getPreTreeNode(root.left);
        map.put(root.val, map.getOrDefault(root.val, 0) + 1);
        getPreTreeNode(root.right);
    }

这是一个有重复数据的二叉搜索树，那么中序遍历也会是一个有序数组

将遍历数据放入map中，个数就统计出来了，根据个数，进行判断最大的次数是多少个,最后进行结果输出

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

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

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

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

该题找最近公共祖先，所有节点的值都是唯一的，p、q 为不同节点且均存在于给定的二叉树中。（题目给出）

有三种情况：

二叉树：[1,2,3]
p:2,q:3 p在左子树，q在右子树,有一个共同父节点1.

二叉树[1,null,2,null,null,3,4]

p:2,q:3 p是父节点.

二叉树[1,2,null,3,4]

p:1,q:2 q是父节点.

遍历整个二叉树，当碰到p,q节点即返回

对左节点和右节点进行比较，

1. 如果都为空，说明该节点没找到
2. 如果都不为空，说明该节点就是父节点
3. 如果某一个节点不为空，返回该节点（会返回到开始节点，说明这两个节点都在同一个树上）