剑指offer-面试题8

不念不忘少年蓝@ 2024-04-19 08:21 72阅读 0赞

## 1. 基本知识复习 ##

对于二叉树中寻找下一节点是一个重要知识点，首先以中序排序寻找为例，如图：

![format_png][]

在上图中中序遍历序列为\{ `d`，`b`，`h`，`e`，`i`，`a`，`f`，`c`，`g`\}。

现在分为两大种情况：

1.该节点有右孩子，则下一节点为他右子树的中序遍历的第一个值（例如`b`的下一节点为`h`）

2.该节点没有右孩子，则需要去找其父亲节点（反正结果一定是一个父节点或则null）

> 2.1 如果该节点是父亲节点的左孩子，那么下一节点就是该父节点（例如`d`的下一节点是`b`）
> 
> 2.2 如果该节点是父亲节点的右孩子，那么需要沿着父节点向上遍历，直到找到那个是父节点的左孩子的节点，那么下一节点是该父节点。（例如`b`的父节点`a`就是节点`i`的下一节点）
> 
> 2.3 如果遍历到root根节点仍然没有找到是父节点左孩子的节点，那么则返回None （例如节点`g`没有下一节点）

## 2. 面试题8 ##

**题目：**

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

**分析：**

分析过程可以参考前面的基本知识学习。

public TreeLinkNode getNext(TreeLinkNode pNode){ 
    
        // 1，首先判断为空的情况
        if(pNode == null){ 
            return null;
        }
    
        // 2.当前节点有右子节点
        TreeLinkNode curr = pNode;
        if(null != pNode.right){ 
            //则去找最左边的子节点即可
            curr = curr.right;
            while (curr.left!=null){ 
                curr = curr.left;
            }
            return curr;
        // 3.当前节点没有由右子节点
        }else { 
            //就去父节点中找,反正得到的结果一定是一个父节点
            //下面这个可以考虑i节点的下一节点是a的情况
            while(curr.next !=null && curr == curr.next.right){ 
                curr = curr.next;
            }
            return curr.next;
        }
    }

## 3. 小结 ##

上面便是二叉树下一节点的寻找的学习，其中对于第二种情况下需要认证考虑。

参考资料：

*  剑指offer （第二版）
 *  [简书面试题8：二叉树的下一个节点python][8_python]

[format_png]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9yYXcuZ2l0aHVidXNlcmNvbnRlbnQuY29tL3hmbGptL2ltZy9tYXN0ZXIvSW1nLzIwMTkwOTE1MTg0MzA1LnBuZw?x-oss-process=image/format,png
[8_python]: https://www.jianshu.com/p/b459d82e9b7e