当前位置：首页 > news >正文

剑指offer-57、二叉树的下一个节点

news 2026/8/13 13:01:03

题⽬描述

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

复杂的节点结构如下：

java

public class TreeLinkNode { int val; TreeLinkNode left = null; TreeLinkNode right = null; TreeLinkNode next = null; TreeLinkNode(int val) { this.val = val; } }

思路及解答

中序遍历

先找到根节点，然后通过根节点，中序遍历，中序遍历的过程中，对⽐节点，是否等于输⼊的节点，然后获取下⼀个节点放回。注意没有下⼀个节点的时候，应该返回 null ，不能数组越界。

java

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

时间复杂度：O(n)。需要遍历整棵树（O(n)）并在列表中查找节点（最坏O(n)）。
空间复杂度：O(n)。

不借助额外的空间(推荐)

据中序遍历的顺序规则和节点的位置关系，通过指针操作直接定位。

核心思路：中序遍历的顺序是“左-根-右”。给定节点的“下一个节点”取决于它自己的位置情况

分为⼏种情况讨论：

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

java

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