# 树

## 二叉树

使用Java实现二叉树：

```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](https://2351062869-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2F7b2CdwBN9liniVJpfEAc%2Fuploads%2Fgit-blob-a7be3740c068a5535cc54fc28e2a68bd831f1e6f%2Fimage-20220407140438757.png?alt=media)

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

二叉树的遍历分为三种：

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代码实现三种遍历方式：

```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 + " ");
}
```

### 递归序遍历

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

```java
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/>

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

```java
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](https://2351062869-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2F7b2CdwBN9liniVJpfEAc%2Fuploads%2Fgit-blob-c9207e9f4b531da01cbdac609341e2325d59c6e3%2Fimage-20220407153824069.png?alt=media)

1. 头节点不可能破坏镜面关系
2. 头节点下可以分为左右两个子树，他们相同的一层之间的左子树与对方的右子树相同

Java实现如下：

```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/>

```java
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/>

```java
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. 当树的每一层都遍历过了，遍历循环结束

```java
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，并且左数是一个平衡二叉树、右树也是一个平衡二叉树。

```java
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/>

采用递归：

```java
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/>

解法：

```java
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/>

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

```java
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`类，就是优先级队列的实现，默认是一个小根堆（先弹出最小的元素）：

```java
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
    }
}
```


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://yangsx95.gitbook.io/notes/computer-science/shu-ju-jie-gou-he-suan-fa/shu.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.