今天这题有点意思，也是模拟题，题目在这这里

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

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;
}