今天这题有点意思，也是模拟题，题目在这[这里](https://www.acwing.com/problem/content/31/)


![image.png](/static/img/067e3ec306d5449735105a06b7b7282d.image.webp)


借这个机会温习一下二叉树前中后序遍历



### 1. 前序遍历（Preorder Traversal）
前序遍历的顺序是：**根节点 -> 左子树 -> 右子树**。

**例子：**

考虑以下二叉树：

```
       1
      / \
     2   3
    / \   \
   4   5   6
  / \   \
 7   8   9
```

前序遍历的结果是：**1, 2, 4, 7, 8, 5, 9, 3, 6**

**解释：**
- 首先访问根节点 `1`。
- 然后访问左子树，左子树的根节点是 `2`。
- 继续访问 `2` 的左子树，左子树的根节点是 `4`。
- 继续访问 `4` 的左子树，左子树的根节点是 `7`。
- `7` 没有子节点，回溯到 `4`，访问 `4` 的右子树，右子树的根节点是 `8`。
- `8` 没有子节点，回溯到 `4`，再回溯到 `2`，访问 `2` 的右子树，右子树的根节点是 `5`。
- 继续访问 `5` 的右子树，右子树的根节点是 `9`。
- `9` 没有子节点，回溯到 `5`，再回溯到 `2`，再回溯到 `1`，访问 `1` 的右子树，右子树的根节点是 `3`。
- 继续访问 `3` 的右子树，右子树的根节点是 `6`。
- `6` 没有子节点，遍历结束。

### 2. 中序遍历（Inorder Traversal）
中序遍历的顺序是：**左子树 -> 根节点 -> 右子树**。

**例子：**

考虑同样的二叉树：

```
       1
      / \
     2   3
    / \   \
   4   5   6
  / \   \
 7   8   9
```

中序遍历的结果是：**7, 4, 8, 2, 5, 9, 1, 3, 6**

**解释：**
- 首先访问最左边的节点 `7`。
- 然后访问 `7` 的父节点 `4`。
- 继续访问 `4` 的右子树，右子树的根节点是 `8`。
- `8` 没有子节点，回溯到 `4`，再回溯到 `2`，访问 `2`。
- 继续访问 `2` 的右子树，右子树的根节点是 `5`。
- 继续访问 `5` 的右子树，右子树的根节点是 `9`。
- `9` 没有子节点，回溯到 `5`，再回溯到 `2`，再回溯到 `1`，访问 `1`。
- 继续访问 `1` 的右子树，右子树的根节点是 `3`。
- 继续访问 `3` 的右子树，右子树的根节点是 `6`。
- `6` 没有子节点，遍历结束。

### 3. 后序遍历（Postorder Traversal）
后序遍历的顺序是：**左子树 -> 右子树 -> 根节点**。

**例子：**

考虑同样的二叉树：

```
       1
      / \
     2   3
    / \   \
   4   5   6
  / \   \
 7   8   9
```

后序遍历的结果是：**7, 8, 4, 9, 5, 2, 6, 3, 1**

**解释：**
- 首先访问最左边的节点 `7`。
- `7` 没有子节点，回溯到 `4`，访问 `4` 的右子树，右子树的根节点是 `8`。
- `8` 没有子节点，回溯到 `4`，访问 `4`。
- 回溯到 `2`，访问 `2` 的右子树，右子树的根节点是 `5`。
- 继续访问 `5` 的右子树，右子树的根节点是 `9`。
- `9` 没有子节点，回溯到 `5`，访问 `5`。
- 回溯到 `2`，访问 `2`。
- 回溯到 `1`，访问 `1` 的右子树，右子树的根节点是 `3`。
- 继续访问 `3` 的右子树，右子树的根节点是 `6`。
- `6` 没有子节点，回溯到 `3`，访问 `3`。
- 回溯到 `1`，访问 `1`，遍历结束。

### 总结
- **前序遍历**：根节点 -> 左子树 -> 右子树
- **中序遍历**：左子树 -> 根节点 -> 右子树
- **后序遍历**：左子树 -> 右子树 -> 根节点


接下来看题目，题目是中序遍历，**左子树 -> 右子树 -> 根节点**

中序遍历序列的下一个节点可能有以下几种情况：

1. **当前节点有右子树**：下一个节点是右子树的最左节点。
2. **当前节点没有右子树**：下一个节点是沿着父节点向上查找，直到找到一个节点是其父节点的左子节点。

### 代码实现

```java
class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode parent; // 指向父节点的指针

    TreeNode(int x) {
        val = x;
    }
}

public class Solution {

    public TreeNode inorderSuccessor(TreeNode p) {
        if (p == null) {
            return null;
        }

        // 情况1：如果节点 p 有右子树，则下一个节点是右子树的最左节点
        if (p.right != null) {
            p = p.right;
            while (p.left != null) {
                p = p.left;
            }
            return p;
        }

        // 情况2：如果节点 p 没有右子树，则向上查找，直到找到一个节点是其父节点的左子节点
        while (p.parent != null && p == p.parent.right) {
            p = p.parent;
        }
        return p.parent;
    }

  
}
```

第一种情况都很好理解，举个第二种情况的例子



### 示例二叉树
假设我们有以下二叉树：

```
      4
     / \
    2   5
   / \   \
  1   3   6
```

### 中序遍历序列
中序遍历的顺序是：`1 -> 2 -> 3 -> 4 -> 5 -> 6`。

### 情况2：当前节点没有右子树
假设我们给定的节点是 `3`，它没有右子树。我们需要找到 `3` 的中序遍历序列的下一个节点。

1. **当前节点是 `3`**：
   - `3` 没有右子树。
   - 我们需要向上查找，直到找到一个节点是其父节点的左子节点。

2. **向上查找**：
   - `3` 的父节点是 `2`。
   - `3` 是 `2` 的右子节点。
   - 继续向上查找，`2` 的父节点是 `4`。
   - `2` 是 `4` 的左子节点。

3. **找到下一个节点**：
   - `2` 是 `4` 的左子节点，所以 `4` 是 `3` 的中序遍历序列的下一个节点。

### 代码实现
让我们看看代码如何处理这种情况：

```java

    // 情况2：如果节点 p 没有右子树，则向上查找，直到找到一个节点是其父节点的左子节点
    while (p.parent != null && p == p.parent.right) {
        p = p.parent;
    }
    return p.parent;
```

多抄几遍代码哦！

```go
/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 *     Father *TreeNode
 * }
 */
func inorderSuccessor(p *TreeNode) *TreeNode {
    
    if(p == nil) {
        return nil;
    }
    
    // 情况一：有右子树就是右子树的左节点
    if(p.Right != nil){
        p = p.Right
        
        for p.Left != nil {
            p = p.Left
        }
        
        return p;
    }
    
    
    // 情况二
    
    
    for p.Father != nil && p == p.Father.Right {
        p = p.Father;
    }
    
    return p.Father;
}

```


9.13算法题

https://www.acwing.com/problem/content/39/
直接模拟

```java
class Solution {
    public int[] printMatrix(int[][] matrix) {
        if(matrix == null || matrix .length == 0 || matrix[0].length == 0) {
            return new int[0];
        }
        
        int row = matrix.length;
        
        int col = matrix[0].length;
        
        int top = 0;
        int bot = row - 1;
        int left = 0;
        int right = col - 1;
        
        int index = 0;
        
        
        int[] result = new int[row * col];
        
        while(left <= right && top <= bot) {
            for(int i = left; i <= right; i++) {
                result[index++] = matrix[top][i]; 
            }
            
            top++;
            
            for(int i = top; i <= bot; i++) {
                result[index++] = matrix[i][right];
            }
            
            right--;
            
            
            if(top <= bot) {
                for(int i = right; i >= left; i--) {
                    result[index++] = matrix[bot][i];
                }
                
                bot--;
            }
            
            if(left <= right) {
                for(int i = bot; i >= top; i--) {
                    result[index++] = matrix[i][left];
                }
                
                left++;
            }
            
            
        }
        
        return result;
        
    }
}

```

9.11算法题

https://www.acwing.com/problem/content/35/


今天做这题

```java
class Solution {
    public boolean hasSubtree(TreeNode pRoot1, TreeNode pRoot2) {
         if(pRoot1 == null || pRoot2 == null) {
            return false;
        }
        
        return v(pRoot1,pRoot2) || hasSubtree(pRoot1.left,pRoot2) || hasSubtree(pRoot1.right,pRoot2);
    }
    
    private boolean v(TreeNode A,TreeNode B) {
        if(B == null) {
            return true;
        }
        
        if(A == null || A.val != B.val){
            return false;
        }
        
        return v(A.left,B.left) && v(A.right, B.right);
    }
}
```


```go
/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func hasSubtree(pRoot1 *TreeNode, pRoot2 *TreeNode) bool {
    if(pRoot2 == nil || pRoot1 == nil) {
        return false;
    }
    
    return V(pRoot1, pRoot2) || hasSubtree(pRoot1.Left, pRoot2) || hasSubtree(pRoot1.Right, pRoot2);
}


func V(A, B *TreeNode) bool {
    if(B == nil) {
        return true;
    }
    
    if(A == nil || A.Val != B.Val) {
        return false;
    }
    
    return V(A.Left, B.Left) && V(A.Right, B.Right);
}
```

9.12算法题

今天写这题

https://www.acwing.com/problem/content/submission/code_detail/36912299/

```java

class Solution {
    public boolean verifySequenceOfBST(int [] sequence) {
        if (sequence == null || sequence.length == 0) {
            return true;
        }
        return verify(sequence, 0, sequence.length - 1);
    }

    private boolean verify(int[] postorder, int start, int end) {
        if (start >= end) {
            return true;
        }

        int root = postorder[end];
        int i = start;

        // 找到第一个大于根节点的元素，这个元素之前的部分是左子树
        while (i < end && postorder[i] < root) {
            i++;
        }

        // 检查右子树中的所有元素是否都大于根节点
        for (int j = i; j < end; j++) {
            if (postorder[j] < root) {
                return false;
            }
        }

        // 递归检查左子树和右子树
        return verify(postorder, start, i - 1) && verify(postorder, i, end - 1);
    }

}

```



短篇1