首页 > 其他 > 详细

Flatten Binary Tree to Linked List

时间:2014-12-03 21:13:16      阅读:283      评论:0      收藏:0      [点我收藏+]

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
/**
 * Definition for binary tree
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    void flatten(TreeNode *root) {
        TreeNode*now = root;
        while (now)
        {
            if(now->left)
            {
                // Find current node‘s prenode that links to current node‘s right subtree
                TreeNode* pre = now->left;
                while(pre->right)
                {
                    pre = pre->right;
                }
                pre->right = now->right;
                // Use current node‘s left subtree to replace its right subtree(original right 
                // subtree is already linked by current node‘s prenode
                now->right = now->left;
                now->left = NULL;
            }
            now = now->right;
        }
    }
};

 

Flatten Binary Tree to Linked List

原文:http://www.cnblogs.com/code-swan/p/4141164.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!