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

LeetCode:Flatten Binary Tree to Linked List

2024-08-04 06:58:49   219人阅读

题目描述：

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


联系
我们