c - 修改二叉树

Question

给定一个二叉树。以这样的方式修改它，修改后您可以仅使用右指针对其进行预序遍历。在修改过程中，您可以使用右指针和左指针。

有人建议这种方法吗？如果我们用中序代替预序，那么我们可以将树修改为 BST如果我们使用后序遍历而不是先序遍历，该怎么做？

Answer 1

这归结为对树进行线性化。前序遍历访问顺序父节点、左子树、右子树中的节点。如果我们只想使用右指针来完成此操作，则左子树必须为空。这样做的想法是重新排列子树。让右指针指向原来的左子树。然后让这个子树的最后一个节点的右指针指向原来的右子树。

这个想法是这样的:

Node* Linearize(Node* root) // returns the subtree's last node
{
    //if it's a leaf node
    if(root->left == NULL && root->right == NULL)
        return root;

    //if there is no left subtree
    if(root->left == NULL)
        return Linearize(root->right);

    //if there is no right subtree
    if(root->right == NULL)
    {
        root->right = root->left;
        root->left = NULL;
        return Linearize(root->right);
    }

    //both subtrees exist
    Node* left = root->left;
    Node* right = root->right;
    Node* lastOfLeft = Linearize(left);
    root->right = left;
    root->left = NULL;
    lastOfLeft->right = right;
    return Linearize(right);
}