描述

题目描述

给定一个二叉树其中的一个结点，请找出中序遍历顺序的下一个结点并且返回。注意，树中的结点不仅包含左右子结点，同时包含指向父结点的next指针。

输入描述：

输入分为2段，第一段是整体的二叉树，第二段是给定二叉树节点的值，后台会将这2个参数组装为一个二叉树局部的子树传入到函数GetNext里面，用户得到的输入只有一个子树根节点

返回值描述：

返回传入的子树根节点的下一个节点，后台会打印输出这个节点

示例
输入：{8,6,10,5,7,9,11},8
返回值：9

知识点：二叉树，遍历
难度：⭐⭐

题解

解题思路

对于二叉树的问题，无非就是遍历、递归、套框架。

这道题最容易想到的就是暴力遍历，根据结点的值找到结点的下一个结点，好在二叉树不存在重复结点，此法可行，但不是考察重点和最优解。

最有解法是通过使用中序遍历的特性，分类模拟，从而分情况找到结点处于不同状态下的下一个结点的解法。

方法一：特性模拟

图解

image-20210706194502168

算法流程：
  • 1、如果目标结点不是叶子结点
    • 则在中序遍历中，下一个结点为当前结点的右子树的最左叶子结点
    • 循环遍历，找到当前子树的最左叶子结点
  • 2、如果目标结点是叶子结点而不是根节点，则需要向上寻找父节点
    • 结点是父节点的左子结点，则在中序遍历中，目标结点的下一个结点就是父节点
    • 结点是是父节点的右子结点，则在中序遍历中，还要继续寻找， 直到满足当前结点是父节点的左子结点
Java 版本代码如下：
public class Solution {
    public TreeLinkNode GetNext(TreeLinkNode pNode) {
        if(pNode == null) {
            return null;
        }
        // 1、如果目标结点不是叶子结点
        // 则在中序遍历中，下一个结点为当前结点的右子树的最左叶子结点
        if(pNode.right != null) {
            pNode = pNode.right;
            // 循环遍历，找到当前子树的最左叶子结点
            while(pNode.left != null) {
                pNode = pNode.left;
            }
            return pNode;
        }
        // 2、目标结点是叶子结点而不是根节点，则需要向上寻找父节点
        while(pNode.next != null) {
            TreeLinkNode parentNode = pNode.next;
            // 是父节点的左子结点，则在中序遍历中，目标结点的下一个结点就是父节点
            if(parentNode.left == pNode) {
                return parentNode;
            } else {
                // 是父节点的右子结点，则在中序遍历中，还要继续寻找
                // 直到满足当前结点是父节点的左子结点
                pNode = pNode.next;
            }
        }
        return null;
    }
}
Python 版本代码如下：
class Solution:
    def GetNext(self, pNode):
        # write code here
        if not pNode:
            return pNode
        # 1、如果目标结点不是叶子结点
        while pNode.right:
            p=pNode.right
            # 则在中序遍历中，下一个结点为当前结点的右子树的最左叶子结点
            if p.left:
                p=p.left
            return p
        # 2、目标结点是叶子结点而不是根节点，则需要向上寻找父节点
        while pNode.next:
            p=pNode.next
            # 是父节点的右子结点，则在中序遍历中，还要继续寻找,直到满足当前结点是父节点的左子结点
            if p.left==pNode:
                return p
            pNode=p
复杂度分析：

时间复杂度 O(N)：最坏的情况是遍历所有结点
空间复杂度 O(1)：没有用到类似数组的类型数据

方法二：暴力查找

算法流程：

根据二叉树结点都是唯一值的特性，通过目标结点的值查找目标结点，便能找到中序遍历的下一个结点

Java 版本代码如下：
import java.util.*;
public class Solution {
    static ArrayList<TreeLinkNode> list = new ArrayList<>();
    public TreeLinkNode GetNext(TreeLinkNode pNode){
        TreeLinkNode par = pNode;
        while(par.next != null){
            par = par.next;
        }
        InOrder(par);
        for(int i=0;i<list.size();i++){
            if(pNode == list.get(i)){
                return i == list.size()-1?null:list.get(i+1);
            }
        }
        return null;
    }
    void InOrder(TreeLinkNode pNode){
        if(pNode!=null){
            InOrder(pNode.left);
            list.add(pNode);
            InOrder(pNode.right);
        }
    }
}
复杂度分析：

时间复杂度 O(N)：最坏的情况是遍历所有结点
空间复杂度 O(N)：用到了集合，N 为 List 长度