[LeetCode] Flatten Binary Tree to Linked List
发布时间:2020-12-14 04:50:06 所属栏目:大数据 来源:网络整理
导读:Given a binary tree,flatten it to a linked list in-place. For example,given the following tree: 1 / 2 5 / 3 4 6 The flattened tree should look like: 1 2 3 4 5 6 将一个二叉树重组成一个链表 题目要求按照二叉树的先序遍历的顺序重组二叉树 思路
Given a binary tree,flatten it to a linked list in-place. For example,given the following tree: 1 / 2 5 / 3 4 6 The flattened tree should look like: 1 2 3 4 5 6 将一个二叉树重组成一个链表 题目要求按照二叉树的先序遍历的顺序重组二叉树 思路1: 找到最左侧结点,将其父结点与父结点右结点断开,将其连接至父结点右侧,变成父结点的右结点,然后把原右结点插入到新右结点的右侧。递归这一操作即可 /** * Definition for a binary tree node. * 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) return; if (root->left) flatten(root->left); if (root->right) flatten(root->right); TreeNode* temp = root->right; root->right = root->left; root->left = NULL; while (root->right) root = root->right; root->right = temp; } }; 思路2: 从根结点出发,判断其左结点是否存在,如果存在,则将根结点与其右结点断开,根的左结点变成其右结点。在将右结点链接至左结点最右边的右结点处。 /** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x),right(NULL) {} * }; */ class Solution { public: void flatten(TreeNode* root) { if (!root) return; TreeNode* curr = root; while (curr) { if (curr->left) { TreeNode* temp = curr->left; while (temp->right) temp = temp->right; temp->right = curr->right; curr->right = curr->left; curr->left = NULL; } curr = curr->right; } } }; (编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |