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:
» Solve this problem
If you notice carefully in the flattened tree, each node's right child points to the next node of a pre-order traversal.
按照道理应该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); } };
相关推荐
leetcode做过的LeetCode的题目记录一下。对一些比较经典的题型进行分类总结。数据结构 数组 字符串 队列 链表 双指针 栈 堆 树 二叉搜索树 字典树 线段树 并查集 哈希表 图基础... Flatten Binary Tree to Linked List
leetcode的题目:Balanced Binary Tree
leetcode 答案leetcode 的工具 这个项目提供了一些工具来更容易地测试 leetcode 答案。 树:切片 <-> TreeNode 此工具有助于将切片转换为 TreeNode,反之亦然。 Slice2TreeNode: []interface{} -> *model....
BinaryTree.py是一个方便的工具,它可以构建和显示编码时所需的二叉树 演示 您需要在使用之前导入该类 import BinaryTree as bt 从值/对象列表或二叉树构造二叉树 t1 = bt.BinaryTree([1,2,3,4,5,'#',6,7,'#','#','#...
Flatten Binary Tree to Linked List Populating Next Right Pointers in Each Node II 二叉树的构建 Construct Binary Tree from Preorder and Inorder Traversal Construct Binary Tree from Inorder and ...
二叉树前序遍历,leetcode
文件中包含了LeetCode中Tag为LinkedList的题目参考代码。
leetcode卡leetcode 二叉树卡片 LeetCode 二叉树卡片问题的章节智解
LeetCode-BinarySearch
这是LeetCode中Linked List所有题目的参考代码。(截止到目前为止:2015年12月14日)。
leetcode-tag-Tree
我的个人微信公众号:Microstrong 微信公众号ID:MicrostrongAI 微信公众号介绍:Microstrong(小强)同学主要研究机器学习、深度学习、计算机视觉、智能对话系统相关内容,分享在学习过程中的...102. Binary Tree Leve
* [Linked List](https://github.com/kamyu104/LeetCode#linked-list) * [Stack](https://github.com/kamyu104/LeetCode#stack) * [Queue](https://github.com/kamyu104/LeetCode#queue) * [Heap]...
144.Binary_Tree_Preorder_Traversal二叉树的前序遍历【LeetCode单题讲解系列】
145.Binary_Tree_Postorder_Traversal二叉树的后序遍历【LeetCode单题讲解系列】
94.Binary_Tree_Inorder_Traversal二叉树的中序遍历【LeetCode单题讲解系列】
leetcode卡除非您已经使用过卡片,否则不要看这里。 做真实的自己!
最大公共字符串leetcode 二叉树 二叉树是一种抽象的数据结构,由根节点和左右子树组成。 一个节点可以有零个、一个或两个子节点。 二叉树的类型 目标 能够熟悉二叉树上的各种术语。 能够实现二叉树节点。 能够使用...
方法1 思路:将链表中的元素都保存list中,并判断这个list和反转后的list,是否相同,如果相同,则回文;否则,则不回文。...# Definition for singly-linked list. # class ListNode(object): # def __i
leetcode卡 LeetCode 记录一下再LeetCode上刷的题,坚持每天刷一道吧 2017.06.12 打卡[LeetCode 2. Add Two Numbers], Linked list 2017.06.13 打卡[LeetCode 200. Number of Islands], BFS 2017.06.14 打卡...