返回先序遍历的最后一个节点

设计算法，返回二叉树T的先序序列的最后一个节点，要求非递归，不能使用栈。

先序遍历先遍历根节点，然后遍历左子树，最后遍历右子树。因此如果有右子树的话，最后一个节点肯定在右子树里面，一直往右走就可以，如果没有右子树的话，最后一个节点肯定在左子树，往左走一步就可以，一直迭代下去直到没有子节点为止。

class TreeNode :
    def __init__(self, x):
        self.left = None
        self.right = None
        self.val = x
class Solution:
    def getLastNodeOfPreorderTravel(self, root):
        tmp = root
        while(tmp):
            if tmp.right:
                tmp = tmp.right
            elif tmp.left:
                tmp = tmp.left
            else:
                break
        return tmp

那么相应的，我们可以设计出算法返回中序遍历序列的最后一个节点。

中序遍历就是先遍历左子树，然后遍历根节点，最后遍历右子树。因此如果没有右子树，那么根节点就是最后一个节点；如果有右子树，最后一个节点就在右子树中。迭代下去，找到没有子节点的节点返回即可。

def getLastNodeOfPreorderTravel(self, root):
    tmp = root
    while(tmp):
        if tmp.right:
            tmp = tmp.right
        else:    
            break
    return tmp

最后，你可能会想如何获得后序遍历的最后一个节点呢？后序遍历顺序是先遍历左子树，后遍历右子树，最后遍历根节点，因此最后一个节点必然是根节点。直接返回即可。