`
cozilla
  • 浏览: 93892 次
  • 性别: Icon_minigender_1
  • 来自: 南京
社区版块
存档分类
最新评论

[Leetcode] Flatten Binary Tree to Linked List

 
阅读更多
Flatten Binary Tree to Linked ListOct 14 '127105 / 21371

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
Hints:

If you notice carefully in the flattened tree, each node's right child points to the next node of a pre-order traversal.

» Solve this problem

按照道理应该1更快,但是实际貌似差不多。

1和2的区别,主要是在对flat( right,xx)的处理上。

/**
 * 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) {
        if (root == NULL) return;
        TreeNode* tail;
        flat(root, tail);
    }
    
    void flat(TreeNode* cur, TreeNode* &tail) {
        
        if (cur->left == NULL && cur->right == NULL) {
            tail = cur;
            return;
        }
        
        if (cur->left != NULL) {
            TreeNode* lefttail;
            flat(cur->left, lefttail);
            lefttail->right = cur->right;
            cur->right = cur->left;
            cur->left = NULL;
            if (lefttail->right == NULL) 
                tail = lefttail;
            else {
                flat(lefttail->right, tail);
            }
        }
        else {
            flat(cur->right, tail);
        }
    }
};

 

 

/**
 * 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) {
        if (root == NULL) return;
        TreeNode* tail;
        flat(root, tail);
    }
    
    void flat(TreeNode* cur, TreeNode* &tail) {
        
        if (cur->left == NULL && cur->right == NULL) {
            tail = cur;
            return;
        }
        
        if (cur->left != NULL) {
            TreeNode* lefttail;
            flat(cur->left, lefttail);
            lefttail->right = cur->right;
            cur->right = cur->left;
            cur->left = NULL;
            
        }
        
        flat(cur->right, tail);
        
    }
};

 

分享到:
评论

相关推荐

    java-leetcode-114-flatten-binary-tree-to-linked-list

    java java_leetcode-114-flatten-binary-tree-to-linked-list

    python-leetcode题解之114-Flatten-Binary-Tree-to-Linked-List

    1. 题目概述:leetcode的第114题是关于将二叉树展平为链表的问题,要求将一个给定的二叉树按照前序遍历的顺序重构为链表形式。 2. 前序遍历:前序遍历是树的一种遍历方法,按照根节点、左子树、右子树的顺序访问树...

    js-leetcode题解之114-flatten-binary-tree-to-linked-list.js

    在前端开发中,算法和数据结构是基础知识,而LeetCode是一个旨在帮助开发者准备技术面试的平台。LeetCode上有许多题目可以帮助开发者训练和提升编程能力。114号题目要求将二叉树展开为链表,这是一个二叉树遍历的...

    leetcode:leetcode解题

    leetcode做过的LeetCode的题目记录一下。对一些比较经典的题型进行分类总结。数据结构 数组 字符串 队列 链表 双指针 栈 堆 树 二叉搜索树 字典树 线段树 并查集 哈希表 图基础... Flatten Binary Tree to Linked List

    leetcode答案-leetcode-tools:leetcode-工具

    leetcode 答案leetcode 的工具 这个项目提供了一些工具来更容易地测试 leetcode 答案。 树:切片 <-> TreeNode 此工具有助于将切片转换为 TreeNode,反之亦然。 Slice2TreeNode: []interface{} -> *model....

    Leetcode题目+解析+思路+答案.pdf

    - **Flatten Binary Tree to Linked List**:将二叉树展平为单链表。 - **Validate Binary Search Tree**:验证一个二叉树是否为二叉搜索树。 - **Recover Binary Search Tree**:恢复二叉搜索树中的两个错误节点...

    LeetCode最全代码

    * [Linked List](https://github.com/kamyu104/LeetCode#linked-list) * [Stack](https://github.com/kamyu104/LeetCode#stack) * [Queue](https://github.com/kamyu104/LeetCode#queue) * [Heap]...

    leetcode-answer-and-analysis(part).zip_图形图像处理_Java_

    5. **Flatten Binary Tree to Linked List** (二叉树展开为链表): 这是一个关于树的层次遍历的问题,可以使用广度优先搜索(BFS)策略,利用队列(如Java的`Queue`接口)来实现。 6. **Merge Sorted Array** (合并...

    leetcode92java-Algorithms::memo:在这里你可以找到我在算法和数据结构方面的进展

    flatten_binary_tree_to_linked_list Java 中等的 100.00% 100.00% binary_tree_pruning Java 中等的 100.00% 100.00% insert_into_a_binary_search_tree Java 中等的 100.00% 100.00% maximum_level_sum_of_a_...

    Tree and Divide Conquer

    **三、Flatten Binary Tree to Linked List** LeetCode的第114题,要求将二叉树扁平化为单链表,这个问题可以通过分治策略解决。基本步骤如下: 1. **从最简单的case开始**:对于只有一个元素的树,直接返回,即空...

Global site tag (gtag.js) - Google Analytics