剑指offer-57、二叉树的下一个节点
<h2 id="题描述">题⽬描述</h2><p>给定⼀个⼆叉树和其中的⼀个结点，请找出中序遍历顺序的下⼀个结点并且返回。注意，树中的结点不仅包含左右⼦结点，同时包含指向⽗结点的指针。</p>
<p>复杂的节点结构如下：</p>
<pre><code class="language-java">public class TreeLinkNode {
int val;
TreeLinkNode left = null;
TreeLinkNode right = null;
TreeLinkNode next = null;
TreeLinkNode(int val) {
this.val = val;
}
}
</code></pre>
<h2 id="思路及解答">思路及解答</h2>
<h3 id="中序遍历">中序遍历</h3>
<p>先找到根节点，然后通过根节点，中序遍历，中序遍历的过程中，对⽐节点，是否等于输⼊的节点，然后获取下⼀个节点放回。注意没有下⼀个节点的时候，应该返回 null ，不能数组越界。</p>
<pre><code class="language-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);
}
}
}
</code></pre>
<ul>
<li><strong>时间复杂度</strong>：O(n)。需要遍历整棵树（O(n)）并在列表中查找节点（最坏O(n)）。</li>
<li><strong>空间复杂度</strong>：O(n)。</li>
</ul>
<h3 id="不借助额外的空间推荐">不借助额外的空间(推荐)</h3>
<p>据中序遍历的顺序规则和节点的位置关系，通过指针操作直接定位。</p>
<p><strong>核心思路</strong>：中序遍历的顺序是“左-根-右”。给定节点的“下一个节点”取决于它自己的位置情况</p>
<p>分为⼏种情况讨论：</p>
<ul>
<li>当前节点为空，直接返回空</li>
<li>当前节点不为空：
<ul>
<li>如果当前节点的右节点不为空，那么下⼀个节点就是右节点的最左⼦孙节点。</li>
<li>如果当前节点的右节点为空，那么只能到⽗节点：
<ul>
<li>需要判断当前节点是不是⽗节点的左节点，如果是⽗节点的左节点，那么下⼀个节点就是⽗节点。</li>
<li>如果当前节点不是⽗节点的左节点，那么就是⽗节点的右节点，也就是下⼀个节点应该是⽗节点的⽗节点，或者更上⼀层。这个怎么判断呢？根据当前节点是不是右节点来判断，如果是右节点，则还需要往⽗节点的上⾛⼀层，如果不是右节点，则直接放回⽗节点。</li>
</ul>
</li>
</ul>
</li>
</ul>
<pre><code class="language-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;
}
</code></pre>
<ul>
<li><strong>时间复杂度</strong>：O(k)。<code>k</code>是到后继节点的路径长度，最坏情况为树高O(h)，通常远小于n。</li>
<li><strong>空间复杂度</strong>：O(1)。只使用了固定数量的指针。</li>
</ul>
<p>为了更直观地理解这两种情况，我们可以看一个例子。下图中，节点 <code>5</code>的下一个节点是 <code>6</code>（对应情况1，找右子树的最左节点），节点 <code>7</code>的下一个节点是 <code>8</code>（对应情况2，向上找到第一个作为左子节点的祖先节点的父节点）。</p>
<pre><code class="language-java"> 8
/ \
6 10
/ \/ \
57 911
</code></pre>
</div>
<div id="MySignature" role="contentinfo">
<p>本文来自在线网站：seven的菜鸟成长之路，作者：seven，转载请注明原文链接：www.seven97.top</p><br><br>
来源：https://www.cnblogs.com/sevencoding/p/19411437
頁:
[1]