题解 | #二叉树的下一个结点#
二叉树的下一个结点
http://www.nowcoder.com/practice/9023a0c988684a53960365b889ceaf5e
算法思想一：暴力法
解题思路：
直接模拟题意。题意需要找到某个结点中序遍历的下一个结点，那很显然可以这样：
1、根据给出的结点求出整棵树的根节点
2、根据根节点递归求出树的中序遍历，存入res中
3、在res中查找当前结点，则当前结点的下一结点即为所求。
1、根据给出的结点求出整棵树的根节点
2、根据根节点递归求出树的中序遍历，存入res中
3、在res中查找当前结点，则当前结点的下一结点即为所求。
1、当找到当前结点是数组最后一个元素，则直接返回 None/Null
2、当找到当前结点不是数组最后一个元素，则返回下一个数组结点
二叉树中序遍历（DBHEIAFCG）图例：
代码展示：
Python版本
class Solution: def GetNext(self, pNode): # write code here # 中序遍历存储数组 res = [] cur = pNode while cur.next: cur = cur.next self.inorder(cur, res) for i in range(len(res)): if pNode == res[i]: # 判断 i 是不是最后一个结点，是则返回none，否则返回下一个数组结点 return None if i == len(res)-1 else res[i+1] return None # 递归遍历中序 def inorder(self, cur, res): if cur: self.inorder(cur.left, res) res.append(cur) self.inorder(cur.right, res)
复杂度分析：
时间复杂度O(N)：N表示树的结点数量，递归遍历整个树结点，查找遍历数组，最差情况都是O(N)
空间复杂度O(N)：存储二叉树中序遍历数组res占用空间O(N)
算法思想二：最优解法
解题思路：
仔细观察，可以把中序（DBHEIAFCG）下一结点归为几种类型：
1、有右子树，下一结点是右子树中的最左结点，例如 B，下一结点是 H
2、无右子树，且结点是该结点父结点的左子树，则下一结点是该结点的父结点，例如 H，下一结点是 E
3、无右子树，且结点是该结点父结点的右子树，则一直沿着父结点追朔，直到找到某个结点是其父结点的左子树，如果存在这样的结点，那么这个结点的父结点就是我们要找的下一结点。例如 I，下一结点是 A；例如 G，并没有符合情况的结点，所以 G 没有下一结点
1、有右子树，下一结点是右子树中的最左结点，例如 B，下一结点是 H
2、无右子树，且结点是该结点父结点的左子树，则下一结点是该结点的父结点，例如 H，下一结点是 E
3、无右子树，且结点是该结点父结点的右子树，则一直沿着父结点追朔，直到找到某个结点是其父结点的左子树，如果存在这样的结点，那么这个结点的父结点就是我们要找的下一结点。例如 I，下一结点是 A；例如 G，并没有符合情况的结点，所以 G 没有下一结点
代码展示：
JAVA版本
public class Solution {
public TreeLinkNode GetNext(TreeLinkNode pNode)
{
if(pNode == null) return null;
//如果当前结点的右子树是不为空
if(pNode.right != null){
pNode = pNode.right;
while(pNode.left != null)
pNode = pNode.left;
return pNode;
}
//当前结点无右子树时，判断结点是父结点的左子树还是右子树
while(pNode.next != null){
if(pNode.next.left == pNode)
return pNode.next;
pNode = pNode.next;
}
return null;
}
} 复杂度分析：
时间复杂度O(N)：N表示树的结点数量，最差情况查找整个二叉树
空间复杂度O1)：不需要额外空间
投递淘天集团等公司10个岗位 >