首页 > 代码库 > LeetCode:Flatten Binary Tree to Linked List

LeetCode:Flatten Binary Tree to Linked List

题目描述:

Given a binary tree, flatten it to a linked list in-place.

For example,
Given

         1
        /        2   5
      / \        3   4   6

The flattened tree should look like:
   1
         2
             3
                 4
                     5
                         6


思路:在flattened tree中,节点的左子节点都为空,右子节点为二叉树先序遍历序列中该节点的前一个节点。所以可以先序遍历二叉树,在遍历的过程中维护一个next指针,一个pre指针。next指针指向当前遍历节点,pre指针指向前一个遍历的节点,令pre->right = next,pre->left = NULL。先序遍历结束后,即可得到要求的flattened tree。


代码:

void flatten(TreeNode *root)
{
    if(root == NULL)
        return;

    stack<TreeNode *> treenode_stack;
    TreeNode * pre;
    TreeNode * next;
    pre = root;
    next = NULL;

    if(root->right != NULL)
        treenode_stack.push(root->right);
    if(root->left != NULL)
        treenode_stack.push(root->left);

    while(!treenode_stack.empty())
    {
        TreeNode * node = treenode_stack.top();
        treenode_stack.pop();
        next = node;
        pre->right = next;
        pre->left = NULL;
        pre = node;
        if(node->right != NULL)
            treenode_stack.push(node->right);
        if(node->left != NULL)
            treenode_stack.push(node->left);
    }
}




LeetCode:Flatten Binary Tree to Linked List