树

二叉树

使用Java实现二叉树：

public class BinaryTree {

    public static class Node {
        public Node(int val) {
            this.val = val;
        }
        public int val;
        public Node left;
        public Node right;
    }

    public static void main(String[] args) {
        Node head = new Node(1);
        head.left = new Node(2);
        head.right = new Node(3);
        head.left.left = new Node(4);
        head.left.right = new Node(5);
        head.right.left = new Node(6);
        head.right.right = new Node(7);
    }
}

上述的代码转换为二叉树图形如下：

image-20220407140438757

前序遍历、中序遍历、后序遍历

二叉树的遍历分为三种：

1. 前序遍历：头、左、右， 1、2、4、5、3、6、7

2. 中序遍历：左、头、右， 4、2、5、1、6、3、7

3. 后续遍历：左、右、头， 4、5、2、6、7、3、1

这里的前序、后序、中序，针对的目标是头节点，头节点在最前面，就是前序。

使用Java代码实现三种遍历方式：

public static void pre(Node node) {
    if (node == null) return;
    System.out.print(node.val + " ");
    pre(node.left);
    pre(node.right);
}

public static void in(Node node) {
    if (node == null) return;
    in(node.left);
    System.out.print(node.val + " ");
    in(node.right);
}

public static void pos(Node node) {
    if (node == null) return;
    pos(node.left);
    pos(node.right);
    System.out.print(node.val + " ");
}

递归序遍历

前序遍历、中序遍历、后序遍历都是对递归序的改造；使用递归序遍历二叉树，每个节点都会被遍历三次，在前中后三个位置每次都打印即是递归序：

public static void f(Node node) {
    if (node == null) return;
    // 1
    System.out.print(node.val + " ");
    f(node.left);
    // 2
    System.out.print(node.val + " ");
    f(node.right);
    // 3
    System.out.print(node.val + " ");
}

结果为 1 2 4 4 4 2 5 5 5 2 1 3 6 6 6 3 7 7 7 3 1 ，如果只保留每个数字第一次出现的情况，那么就是前序遍历：1 2 4 3 6 7；同理，如果保留第二次出现的情况就是中序遍历；保留最后一次出现的情况，那么就是后序遍历。

比较两颗二叉树结构是否完全相同

对应试题：https://leetcode-cn.com/problems/same-tree/

可以使用递归序遍历比较每个节点：

public boolean isSameTree(TreeNode p, TreeNode q) {
    if (p == null ^ q == null) { // 抑或，相同为0(false) 不同为1(true)， p和q有一个为null，一个不为null
        return false;
    }
    if (p == null) { // 如果  p == q == null，代表递归结束
        return true;
    }
    return p.val == q.val && isSameTree(p.left, q.left) && isSameTree(p.right, q.right);
}

判断一颗树是否是镜面树

对应试题：

左右对称的树称为镜面树：

image-20220407153824069

1. 头节点不可能破坏镜面关系

2. 头节点下可以分为左右两个子树，他们相同的一层之间的左子树与对方的右子树相同

Java实现如下：

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

public boolean isMirror(TreeNode p, TreeNode q) {
    if (p == null ^ q == null) {
        return false;
    }
    if (p == null) {
        return true;
    }
    return p.val == q.val && isMirror(p.left, q.right) && isMirror(p.right, q.left);
}

返回一棵树的最大深度

对应试题：https://leetcode-cn.com/problems/maximum-depth-of-binary-tree/

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

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

对应试题：https://leetcode-cn.com/problems/construct-binary-tree-from-preorder-and-inorder-traversal/

public TreeNode buildTree(int[] preorder, int[] inorder) {
    if (preorder == null || inorder == null || preorder.length == 0) {
        return null;
    }

    return f(preorder, 0, preorder.length - 1, inorder, 0, preorder.length - 1);
}

private TreeNode f(int[] preorder, int l1, int r1, int[] inorder, int l2, int r2) {
    if (l1 > r1) {
        return null;
    }
    if (l1 == r1) {
        return new TreeNode(preorder[l1]);
    }
    int root = preorder[l1];
    int find = 0;
    while (inorder[find] != root) {
        find++;
    }
    TreeNode rootNode = new TreeNode(root);
    rootNode.left = f(preorder, l1 + 1, l1 + find - l2, inorder, l2, find - 1);
    rootNode.right = f(preorder, l1 + find - l2 + 1, r1, inorder, find + 1, r2);
    return rootNode;
}

二叉树按层遍历并收集节点

对应试题：https://leetcode-cn.com/problems/binary-tree-level-order-traversal/

解题思路：

1. 从树的头开始遍历，将头加入到目标队列中

2. 遍历队列中的所有元素，将其弹出

3. 将弹出的所有元素的子结点放入到队列中，跳转2步骤

4. 当树的每一层都遍历过了，遍历循环结束

class Solution {

    public List<List<Integer>> levelOrder(TreeNode root) {
        if (root == null) {
            return Collections.emptyList();
        }

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

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

        while (!queue.isEmpty()) {
            List<TreeNode> ceng = new ArrayList<>();

            while (!queue.isEmpty()) {
                ceng.add(queue.poll());
            }

            ceng.forEach(e -> {
                if (e.left != null) {
                    queue.add(e.left);
                }
                if (e.right != null) {
                    queue.add(e.right);
                }
            });
            result.add(ceng.stream().map(e -> e.val).toList());
        }

        return result;
    }

}

判断树是否是平衡二叉树

对应leetcode：https://leetcode-cn.com/problems/balanced-binary-tree/

平衡二叉树：在一个二叉树中，每一颗子树的左子树的深度与右子树的深度 <= 1，并且左数是一个平衡二叉树、右树也是一个平衡二叉树。

public boolean isBalanced(TreeNode root) {
    return getNodeInfo(root).isBalanced;
}
public Info getNodeInfo(TreeNode node) {
    if (node == null) {
        return new Info(true, 0);
    }
    Info leftInfo = getNodeInfo(node.left);
    Info rightInfo = getNodeInfo(node.right);
    return new Info(
            leftInfo.isBalanced && rightInfo.isBalanced && Math.abs(leftInfo.height - rightInfo.height) <= 1,
            Math.max(leftInfo.height, rightInfo.height) + 1);
}
static class Info {
    public boolean isBalanced; // 是平衡树
    public int height; // 树的高度
    public Info(boolean isBalanced, int height) {
        this.isBalanced = isBalanced;
        this.heig
ht = height;
    }
}

判断树是否是搜索二叉树

在一个树中，每一颗子树的左树的值都比当前值小，右树的值都比当前值大。

判断一个二叉树是否是搜索二叉树：

1. 采用中序遍历，如果是搜索二叉树，中序遍历的结果是递增的

2. 采用递归（左树是搜索二叉树、右树是搜索二叉树，且左树的根节点小于当前值，右树的根节点大于当前值）

对应leetcode：https://leetcode.cn/problems/validate-binary-search-tree/

采用递归：

public boolean isValidBST(TreeNode root) {
    return isBinarySearchTree(root).isBST;
}

private Info isBinarySearchTree(TreeNode node) {
    if (node == null) {
        return null;
    }
    Info leftInfo = isBinarySearchTree(node.left);
    Info rightInfo = isBinarySearchTree(node.right);

    int max = node.val;
    int min = node.val;
    boolean isBST = true;

    if (leftInfo != null) {
        max = Math.max(max, leftInfo.max);
        min = Math.min(min, leftInfo.min);
        isBST = leftInfo.isBST && (leftInfo.max < node.val);
    }
    if (rightInfo != null) {
        max = Math.max(max, rightInfo.max);
        min = Math.min(min, rightInfo.min);
        isBST = isBST && rightInfo.isBST && (rightInfo.min > node.val);
    }

    return new Info(max, min, isBST);
}

static class Info {
    public int max;
    public int min;
    public boolean isBST;
    public Info(int max, int min, boolean isBST) {
        this.max = max;
        this.min = min;
        this.isBST = isBST;
    }
}

二叉树路径总和

对应Leetcode：https://leetcode.cn/problems/path-sum/

解法：

class Solution {
    public boolean hasPathSum(TreeNode root, int targetSum) {
        if (root == null) {
            return false;
        }
        return process(root, targetSum, 0);
    }

    public boolean process(TreeNode node, int targetSum, int sum) {
        // 叶子节点
        if (node.left == null && node.right == null) {
            return targetSum == sum + node.val;
        }
        
        boolean result = false;
        if (node.left != null) {
            result |= process(node.left, targetSum, sum + node.val);
        }

        if (node.right != null)  {
            result |=  process(node.right, targetSum, sum + node.val);
        }

        return result;
    }
}

二叉树收集达标路径总和

Leetcode: https://leetcode.cn/problems/path-sum-ii/

解法（自己独立写的性能很差）：

class Solution {

    private static List<List<Integer>> pathList = null;

    public List<List<Integer>> pathSum(TreeNode root, int targetSum) {
        pathList = new ArrayList<>();
        if (root == null) {
            return new ArrayList<>();
        }
        process(root, targetSum, 0, new ArrayList<>());
        return pathList;
    }

    public void process(TreeNode node, int targetSum, int sum, List<Integer> path) {
        // 无论是叶子节点还是非叶子节点，都要加入到path中
        path.add(node.val);

        // 如果是叶子节点，判断是否符合路径和，如果符合就加入路径到路径列表
        if (node.left == null && node.right == null) {
            if (targetSum == sum + node.val) {
                pathList.add(path);
            }
            return;
        }

        // 如果不是叶子节点
        if (node.left != null) {
            process(node.left, targetSum, sum + node.val, new ArrayList<>(path));
        }

        if (node.right != null) {
            process(node.right, targetSum, sum + node.val, new ArrayList<>(path));
        }
    }
}

堆

优先级队列

定义：优先级队列是不同于先进先出队列的另一种队列。每次从队列中取出的是具有最高优先权的元素。

优先级队列的逻辑存储结构并不是队列，他是一种具有FIFO特征的堆结构（也就是树形结构）。每次从优先级队列中取出的是具有最高优先权的元素，内部按照优先权堆数据元素排序。

比如在Java中的PriorityQueue类，就是优先级队列的实现，默认是一个小根堆（先弹出最小的元素）：

public static void main(String[] args) {
    PriorityQueue<Integer> heap = new PriorityQueue<>();
    heap.add(6);
    heap.add(2);
    heap.add(3);
    heap.add(1);
    heap.add(7);

    while (!heap.isEmpty()) {
        System.out.print(heap.poll() + " "); // 1 2 3 6 7
    }
}