## Go Mod换源

```
# Go Modules機能を有効にする
go env -w GO111MODULE=on

# GOPROXY環境変数を設定する（以下から一つ選択）

# 1. 七牛 CDN
go env -w  GOPROXY=https://goproxy.cn,direct

# 2. 阿里云
go env -w GOPROXY=https://mirrors.aliyun.com/goproxy/,direct

# 3. 公式
go env -w  GOPROXY=https://goproxy.io,direct

```
## Gem换源

```
gem sources # ミラーソースを確認

gem sources --remove https://rubygems.org # デフォルトのソースを削除

gem sources -a https://gems.ruby-china.com # 新しいソースを追加

gem sources --add https://mirrors.tuna.tsinghua.edu.cn/rubygems/ # 別のソースを追加

gem sources -u # ソースを更新
```

各种镜像源

二叉树前中后序遍历习题

2013.7阅读精读

今天这题有点意思，也是模拟题，题目在这[这里](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;
        
    }
}

```

Go Mod换源

短篇1