是否有可能让节点在当前节点之上？

Question

我被问到一个问题，当我遍历我的二叉树时，是否有可能获得当前节点上方的节点？作为双链表。

Answer 1

如果您将其构建为双链接，那么转到“父”属性。抽象示例：

struct node { 
    struct node *parent; // << this is the parent, just access it 
    struct node *rchild; 
    struct node *lchild; 
    int val; 
} 

否则，您需要在每次访问子节点时缓存上一个节点。

注意，一个双链接列表是不一样的二进制树（在列表中的每个项目都有一个孩子）。