剑指Offer（五十七）-- 二叉树的下一个节点

秦怀杂货店

发布于 2022-02-15 14:06:01

2180

发布于 2022-02-15 14:06:01

文章被收录于专栏：技术杂货店

Github仓库地址：https://github.com/Damaer/CodeSolution 笔记地址：https://damaer.github.io/CodeSolution/ 仓库介绍：刷题仓库：CodeSolution

题目描述

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

复杂的节点结构如下：

public class TreeLinkNode {
    int val;
    TreeLinkNode left = null;
    TreeLinkNode right = null;
    TreeLinkNode next = null;

    TreeLinkNode(int val) {
        this.val = val;
    }
}

思路以及解答

第一种思路是先通过循环，先找到根节点，然后通过根节点，中序遍历，中序遍历的过程中，对比节点，是否等于输入的节点，然后获取下一个节点放回。注意没有下一个节点的时候，应该返回null，不能数组越界。

import java.util.ArrayList;
import java.util.List;

public class Solution {
    private static List<TreeLinkNode> treeLinkNodes = new ArrayList<>();

    public TreeLinkNode GetNext(TreeLinkNode pNode) {
        if (pNode != null) {
            TreeLinkNode root = pNode;
            // 一直找到根节点
            while (root != null && root.next != null) {
                root = root.next;
            }
            inOrder(root);
            for (int i = 0; i < treeLinkNodes.size(); i++) {
                if (treeLinkNodes.get(i) == pNode) {
                    return i + 1 < treeLinkNodes.size() ? treeLinkNodes.get(i + 1) : null;
                }
            }
        }
        return null;
    }
    // 中序遍历
    public void inOrder(TreeLinkNode pNode) {
        if (pNode != null) {
            inOrder(pNode.left);
            treeLinkNodes.add(pNode);
            inOrder(pNode.right);
        }
    }
}

上面的做法借助了list，空间复杂度是O(n)，时间上，遍历了两次，也是O(n)的时间复杂度。

另外一种做法是，不借助额外的空间，直接查找下一个节点。分为几种情况讨论：

当前节点为空，直接返回空
当前节点不为空：
- 需要判断当前节点是不是父节点的左节点，如果是父节点的左节点，那么下一个节点就是父节点。
- 如果当前节点不是父节点的左节点，那么就是父节点的右节点，也就是下一个节点应该是父节点的父节点，或者更上一层。这个怎么判断呢？根据当前节点是不是右节点来判断，如果是右节点，则还需要往父节点的上走一层，如果不是右节点，则直接放回父节点。
- 如果当前节点的右节点不为空，那么下一个节点就是右节点的最左子孙节点。
- 如果当前节点的右节点为空，那么只能到父节点：

代码实现如下：

        public TreeLinkNode GetNext(TreeLinkNode pNode) {
            // 右节点不为空，直接找右节点的最左子孙节点
            if (pNode.right != null) {
                TreeLinkNode pRight = pNode.right;
                while (pRight.left != null) {
                    pRight = pRight.left;
                }
                return pRight;
            }
            // 右节点为空，但是当前节点是左节点，下一个就是其父节点
            if (pNode.next != null && pNode.next.left == pNode) {
                return pNode.next;
            }
            // 3.右节点为空，并且当前节点是右节点，那只能往上走
            if (pNode.next != null) {
                // 获取父节点
                TreeLinkNode pNext = pNode.next;
                // 判断父节点是不是同样是右节点，如果是，还需要往上走，如果不是，就可以直接放回其
                while (pNext.next != null && pNext.next.right == pNext) {
                    pNext = pNext.next;
                }
                return pNext.next;
            }
            return null;
        }

时间复杂度：O(n) 空间复杂度：O(1)

【作者简介】：

秦怀，公众号【秦怀杂货店】作者，技术之路不在一时，山高水长，纵使缓慢，驰而不息。个人写作方向：Java源码解析，JDBC，Mybatis，Spring，redis，分布式，剑指Offer，LeetCode等，认真写好每一篇文章，不喜欢标题党，不喜欢花里胡哨，大多写系列文章，不能保证我写的都完全正确，但是我保证所写的均经过实践或者查找资料。遗漏或者错误之处，还望指正。

平日时间宝贵，只能使用晚上以及周末时间学习写作 - END -

本文参与腾讯云自媒体同步曝光计划，分享自微信公众号。

原始发表：2021-03-22，如有侵权请联系 cloudcommunity@tencent.com 删除

编程算法