今日算法05二叉树的下一个结点

2023年 7月 19日 29.5k 0

一、题目描述

题目链接:牛客网

难易程度:中等

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

public class TreeLinkNode {
​
    int val;
    TreeLinkNode left = null;
    TreeLinkNode right = null;
    TreeLinkNode next = null; // 指向父结点的指针
​
    TreeLinkNode(int val) {
        this.val = val;
    }
}

二、解题思路

我们先来回顾一下中序遍历的过程:先遍历树的左子树,再遍历根节点,最后再遍历右子树。所以最左节点是中序遍历的第一个节点。

这个遍历过程如下图所示:

代码如下:

void traverse(TreeNode root) {
    if (root == null) return;
    traverse(root.left);
    visit(root);
    traverse(root.right);
}

① 如果一个节点的右子树不为空,那么该节点的下一个节点是右子树的最左节点;

② 否则,向上找第一个左链接指向的树包含该节点的祖先节点。

三、代码实现

public TreeLinkNode GetNext(TreeLinkNode pNode) {
    if (pNode.right != null) {
        TreeLinkNode node = pNode.right;
        while (node.left != null)
            node = node.left;
        return node;
    } else {
        while (pNode.next != null) {
            TreeLinkNode parent = pNode.next;
            if (parent.left == pNode)
                return parent;
            pNode = pNode.next;
        }
    }
    return null;
}

推荐阅读

  • 今日算法04-重建二叉树

封面

今日算法系列,题解更新地址:studeyang.tech/2023/0719.h…

相关文章

JavaScript2024新功能:Object.groupBy、正则表达式v标志
PHP trim 函数对多字节字符的使用和限制
新函数 json_validate() 、randomizer 类扩展…20 个PHP 8.3 新特性全面解析
使用HTMX为WordPress增效:如何在不使用复杂框架的情况下增强平台功能
为React 19做准备:WordPress 6.6用户指南
如何删除WordPress中的所有评论

发布评论