非递归遍历 带有父节点的二叉树，空间复杂度为O(1)

算法

当进行回溯根节点时now = now->pParent记录旧的子节点last == now; now = now->pParent，以免重复遍历子节点，以查找其父节点

#include <iostream>
using namespace std;
struct Node{
    int key;
    Node* pLeftChild;
    Node* pRightChild;
    Node* pParent;
};
int getHeight(Node* root){
    if(root == NULL)
        return 0;
    Node* last = root;
    Node* now = root;
    int mmax=0;
    int c=1;
    // 根节点由右孩子，但已经访问过
    while(now) {
        while(now->pLeftChild!=NULL && now->pRightChild!=last && now->pLeftChild!=last){
            now = now->pLeftChild;
            c++;
        }
        mmax = c>mmax? c:mmax;
        printf("%d %d\n", c, now->key);
        while(now!=NULL && now->pRightChild==NULL){
            last = now;
            now = now->pParent;
            c--;
        }
        // 根节点无右孩子
        if(now==NULL)
            break;
        if(last != now->pRightChild){
            now = now->pRightChild;
            c++;
        }else{
            last = now;
            now = now->pParent;
            c--;
        }
    }
    return mmax;
}
Node* initTree(){
    int n=0;
    cin>>n;
    if(n==0)
        return NULL;
    Node* p = new Node();
    p->key = n;
    p->pLeftChild = initTree();
    if(p->pLeftChild)
        p->pLeftChild->pParent = p;
    p->pRightChild = initTree();
    if(p->pRightChild)
        p->pRightChild->pParent = p;
    return p;
}
int main(){
    int p=0;
    Node* pTree = initTree();
    p = getHeight(pTree);
    cout<< p << endl;
    return 0;
}
// 1 5 22 0 0 14 0 31 0 0 9 8 98 0 0 0 7 0 0