【剑指 の 精选】详解「二叉树中序遍历的下一个结点」两种解法 ｜Python 主题月

输入:{8,6,10,5,7,9,11},8
返回:9
解析:这个组装传入的子树根节点，其实就是整颗树，中序遍历{5,6,7,8,9,10,11}，根节点8的下一个节点就是9，应该返回{9,10,11}，后台只打印子树的下一个节点，所以只会打印9，如下图，其实都有指向左右孩子的指针，还有指向父节点的指针，下图没有画出来。
复制代码

输入：{8,6,10,5,7,9,11},8
返回值：9
复制代码

输入：{8,6,10,5,7,9,11},6
返回值：7
复制代码

输入：{1,2,#,#,3,#,4},4
返回值：1
复制代码

输入：{5},5
返回值："null"
说明：不存在，后台打印"null" 
复制代码

import java.util.*;
public class Solution {
    List<TreeLinkNode> list = new ArrayList<>();
    public TreeLinkNode GetNext(TreeLinkNode pNode) {
        // 根据传入的节点的 next 指针一直往上找，直到找到根节点 root
        TreeLinkNode root = pNode;
        while (root.next != null) root = root.next;
        // 对树进行一遍「中序遍历」，保存结果到 list 中
        dfs(root);
        // 从 list 中找传入节点 pNode 的位置 idx
        int n = list.size(), idx = -1;
        for (int i = 0; i < n; i++) {
            if (list.get(i).equals(pNode)) {
                idx = i;
                break;
            }
        }
        // 如果 idx 不为「中序遍历」的最后一个元素，那么说明存在下一个节点，从 list 查找并返回
        // 这里的 idx == -1 的判断属于防御性编程
        return idx == -1 || idx == n - 1 ? null : list.get(idx + 1);
    }
    void dfs(TreeLinkNode root) {
        if (root == null) return;
        dfs(root.left);
        list.add(root);
        dfs(root.right);
    }
}
复制代码

class Solution:
    lt = []
    def GetNext(self, pNode):
        # 根据传入的节点的 next 指针一直往上找，直到找到根节点 root
        root = pNode
        while root.next is not None:
            root = root.next
        # 对树进行一遍「中序遍历」，保存结果到 list 中
        self.dfs(root)
        # 从 list 中找传入节点 pNode 的位置 idx
        n = len(self.lt)
        idx = -1
        for i in range(n):
            if self.lt[i] == pNode:
                idx = i
                break
        # 如果 idx 不为「中序遍历」的最后一个元素，那么说明存在下一个节点，从 list 查找并返回
        # 这里的 idx == -1 的判断属于防御性编程
        return None if idx == -1 or idx == n -1 else self.lt[idx + 1]
    def dfs(self, root):
        if root is None:
            return
        self.dfs(root.left)
        self.lt.append(root)
        self.dfs(root.right)
复制代码

public class Solution {
    public TreeLinkNode GetNext(TreeLinkNode pNode) {
        if (pNode.right != null) {
            // 如果当前节点有右儿子，下一节点为当前节点「右子树中最靠左的节点」
            pNode = pNode.right;
            while (pNode.left != null) pNode = pNode.left;
            return pNode;
        } else {
            // 如果当前节点没有右儿子，则「往上找父节点」，直到出现满足「其左儿子是当前节点」的父节点
            while (pNode.next != null) {
                if (pNode.equals(pNode.next.left)) return pNode.next;
                pNode = pNode.next;
            }
        }
        return null;
    }
}
复制代码

class Solution:
    def GetNext(self, pNode):
        if pNode.right is not None:
            # 如果当前节点有右儿子，下一节点为当前节点「右子树中最靠左的节点」
            pNode = pNode.right
            while pNode.left is not None:
                pNode = pNode.left
            return pNode
        else:
            #  如果当前节点没有右儿子，则「往上找父节点」，直到出现满足「其左儿子是当前节点」的父节点
            while pNode.next is not None:
                if pNode == pNode.next.left:
                    return pNode.next
                pNode = pNode.next
        return None
复制代码