二叉树的下一个节点——《剑指offer》

1. 题目描述：给定一个二叉树和其中一个节点，如何找出中序遍历的下一个节点？树中的节点除了有两个分别指向左、右子节点的指针，还有一个指向夫节点的指针。
2. 思想：①当前节点有右子树时，则下一节点是右子树的最左节点。②当前节点没有右子树，当自己是父节点的左孩子时，则下一个节点是父节点。③当前结点既没有右孩子，自己又不是左孩子时，则找到第一个是左孩子的祖先节点，该节点的父亲结点就是下一个结点。④如果当前结点既没有右孩子，又不是左孩子，又没有父节点时，或没有作为左孩子的祖先节点时，则该结点是中序遍历的最后一个结点。
3. 代码实现：

   class Solution {
   public:
       TreeLinkNode* GetNext(TreeLinkNode* pNode) {
           if(pNode==nullptr)
               return nullptr;
           
           TreeLinkNode* p=pNode,*parent=pNode->next;
           if(pNode->right){
               p=pNode->right;
               while(p->left){
                   p=p->left;
               }
               return p;
           }
           
           while(parent&&parent->left!=p){
               p=parent;
               parent=parent->next;
           }
           return parent;
           
       }
   };

# -*- coding:utf-8 -*-
# class TreeLinkNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
#         self.next = None
class Solution:
    def GetNext(self, pNode):
        if not pNode:  #如果该节点为空
            return None
        
        p=pNode #当前结点
        parent=p.next  #当前结点的父节点
        
        if pNode.right:
            p=pNode.right
            while p.left:
                p=p.left
            return p 
        
        while parent and parent.left !=p :
            p=p.next
            parent=parent.next 
        return parent
        
        

①C++数据成员不能再类或结构内直接用赋值号设置默认值，而python可以。