C++实现LeetCode(114.将二叉树展开成链表)

2024-08-01 13:47:32

[LeetCode] 114. Flatten Binary Tree to Linked List 将二叉树展开成链表

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

click to show hints.

Hints:

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

这道题要求把二叉树展开成链表，根据展开后形成的链表的顺序分析出是使用先序遍历，那么只要是数的遍历就有递归和非递归的两种方法来求解，这里我们也用两种方法来求解。首先来看递归版本的，思路是先利用 DFS 的思路找到最左子节点，然后回到其父节点，把其父节点和右子节点断开，将原左子结点连上父节点的右子节点上，然后再把原右子节点连到新右子节点的右子节点上，然后再回到上一父节点做相同操作。代码如下：

解法一：

class Solution {
public:
    void flatten(TreeNode *root) {
        if (!root) return;
        if (root->left) flatten(root->left);
        if (root->right) flatten(root->right);
        TreeNode *tmp = root->right;
        root->right = root->left;
        root->left = NULL;
        while (root->right) root = root->right;
        root->right = tmp;
    }
};

例如，对于下面的二叉树，上述算法的变换的过程如下：

下面再来看非迭代版本的实现，这个方法是从根节点开始出发，先检测其左子结点是否存在，如存在则将根节点和其右子节点断开，将左子结点及其后面所有结构一起连到原右子节点的位置，把原右子节点连到元左子结点最后面的右子节点之后。代码如下：

解法二：

class Solution {
public:
    void flatten(TreeNode *root) {
        TreeNode *cur = root;
        while (cur) {
            if (cur->left) {
                TreeNode *p = cur->left;
                while (p->right) p = p->right;
                p->right = cur->right;
                cur->right = cur->left;
                cur->left = NULL;
            }
            cur = cur->right;
        }
    }
};

例如，对于下面的二叉树，上述算法的变换的过程如下：

前序迭代解法如下：

解法三：

class Solution {
public:
    void flatten(TreeNode* root) {
        if (!root) return;
        stack<TreeNode*> s;
        s.push(root);
        while (!s.empty()) {
            TreeNode *t = s.top(); s.pop();
            if (t->left) {
                TreeNode *r = t->left;
                while (r->right) r = r->right;
                r->right = t->right;
                t->right = t->left;
                t->left = NULL;
            }
            if (t->right) s.push(t->right);
        }
    }
};

此题还可以延伸到用中序，后序，层序的遍历顺序来展开原二叉树，分别又有其对应的递归和非递归的方法，有兴趣的童鞋可以自行实现。

Github 同步地址：

https://github.com/grandyang/leetcode/issues/114

类似题目：

Flatten a Multilevel Doubly Linked List

参考资料：

https://leetcode.com/problems/flatten-binary-tree-to-linked-list/

https://leetcode.com/problems/flatten-binary-tree-to-linked-list/discuss/37182/my-recursive-solution-is-easy-and-clean

https://leetcode.com/problems/flatten-binary-tree-to-linked-list/discuss/36977/my-short-post-order-traversal-java-solution-for-share

到此这篇关于C++实现LeetCode(114.将二叉树展开成链表)的文章就介绍到这了,更多相关C++实现将二叉树展开成链表内容请搜索我们以前的文章或继续浏览下面的相关文章希望大家以后多多支持我们！

C++实现LeetCode(108.将有序数组转为二叉搜索树)

[LeetCode] 108.Convert Sorted Array to Binary Search Tree 将有序数组转为二叉搜索树 Given an array where elements are sorted in ascending order, convert it to a height balanced BST. For this problem, a height-balanced binary tree is defined as a binary tree in wh
C++实现LeetCode(889.由先序和后序遍历建立二叉树)

[LeetCode] 889. Construct Binary Tree from Preorder and Postorder Traversal 由先序和后序遍历建立二叉树 Return any binary tree that matches the given preorder and postorder traversals. Values in the traversals pre and post are distinct positive integers. Example 1
C++实现LeetCode(105.由先序和中序遍历建立二叉树)

[LeetCode] 105. Construct Binary Tree from Preorder and Inorder Traversal 由先序和中序遍历建立二叉树 Given preorder and inorder traversal of a tree, construct the binary tree. Note: You may assume that duplicates do not exist in the tree. For example, given preor
C++实现LeetCode(106.由中序和后序遍历建立二叉树)

[LeetCode] 106. Construct Binary Tree from Inorder and Postorder Traversal 由中序和后序遍历建立二叉树 Given inorder and postorder traversal of a tree, construct the binary tree. Note: You may assume that duplicates do not exist in the tree. For example, given ino
C++实现LeetCode(109.将有序链表转为二叉搜索树)

[LeetCode] 109.Convert Sorted List to Binary Search Tree 将有序链表转为二叉搜索树 Given a singly linked list where elements are sorted in ascending order, convert it to a height balanced BST. For this problem, a height-balanced binary tree is defined as a binary
C++实现LeetCode(143.链表重排序)

[LeetCode] 143.Reorder List 链表重排序 Given a singly linked list L: L0→L1→-→Ln-1→Ln, reorder it to: L0→Ln→L1→Ln-1→L2→Ln-2→- You may not modify the values in the list's nodes, only nodes itself may be changed. Example 1: Given 1->2->3->4, reorder it t
C++实现LeetCode(142.单链表中的环之二)

[LeetCode] 142. Linked List Cycle II 单链表中的环之二 Given a linked list, return the node where the cycle begins. If there is no cycle, return null. To represent a cycle in the given linked list, we use an integer pos which represents the position (0-indexe
C++实现LeetCode(104.二叉树的最大深度)

[LeetCode] 104. Maximum Depth of Binary Tree 二叉树的最大深度 Given a binary tree, find its maximum depth. The maximum depth is the number of nodes along the longest path from the root node down to the farthest leaf node. Note: A leaf is a node with no child
C++实现LeetCode(114.将二叉树展开成链表)

[LeetCode] 114. Flatten Binary Tree to Linked List 将二叉树展开成链表 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 click to show hints
前端算法题解leetcode114二叉树展开为链表

目录正文解题思路-基础代码实现解题思路-进阶代码实现正文题目地址给你二叉树的根结点 root ,请你将它展开为一个单链表: 展开后的单链表应该同样使用 TreeNode ,其中 right 子指针指向链表中下一个结点,而左子指针始终为 null . 展开后的单链表应该与二叉树先序遍历顺序相同. 示例 1: 输入: root = [1,2,5,3,4,null,6]输出: [1,null,2,null,3,null,4,null,5,null,6] 示例 2: 输入: root
Python编程把二叉树打印成多行代码

题目描述从上到下按层打印二叉树,同一层结点从左至右输出.每一层输出一行. 思路: 1.把每层节点的val值用list存好 2.把每层节点存好: ①计算当层节点的个数,这样就保证下一步每层的结点都被pop光 ②然后依次弹出从左到右的每个节点,然后在list中加入该节点对应的左结点.右节点(如果存在的话) 代码如下: class TreeNode(): def __init__(self,x): self.val = x self.left = None self.right = None def
python将三维数组展开成二维数组的实现

以前写过一篇:python实现把两个二维array叠加成三维array示例这篇文章尝试用"曲线救国"的方法来解决二维数组叠加成三维数组的问题. 但天道有轮回,苍天绕过谁.好不容易把数组叠加在一块儿了,新的需求又出现了:将三维数组展开成二维数组.有借有还,再借不难.今天就来解决把三维数组展开成二维数组的问题. 相对于叠加三维数组,numpy对展开数组支持得很好,只需要用好np.reshape(A,(a,b)) 函数即可. 用到的参数: A:需要被重新组合的数组 (a,b): 各个维度的
Python实现把多维数组展开成DataFrame

如下所示: import numpy as np import pandas as pd ################# 准备数据 ################# a1 = np.arange(1,101) a3 = a1.reshape((2,5,10)) a3 ''' array([[[ 1, 2, 3, 4, 5, 6, 7, 8, 9, 10], [ 11, 12, 13, 14, 15, 16, 17, 18, 19, 20], [ 21, 22, 23, 24, 25, 26
C++实现LeetCode(124.求二叉树的最大路径和)

[LeetCode] 124. Binary Tree Maximum Path Sum 求二叉树的最大路径和 Given a non-empty binary tree, find the maximum path sum. For this problem, a path is defined as any sequence of nodes from some starting node to any node in the tree along the parent-child conn
C C++ LeetCode题解在二叉树中增加一行示例详解

目录题目描述整理题意解题思路分析层序遍历(广度优先搜索) 递归(深度优先搜索) 具体实现复杂度分析代码实现层序遍历(广度优先搜索) 递归(深度优先搜索) 总结题目描述题目链接:623. 在二叉树中增加一行给定一个二叉树的根 root 和两个整数 val 和 depth ,在给定的深度 depth 处添加一个值为 val 的节点行. 注意,根节点 root 位于深度 1 . 加法规则如下: 给定整数 depth,对于深度为 depth - 1 的每个非空树节点 cur ,创建两
C++实现LeetCode(23.合并k个有序链表)

[LeetCode] 23. Merge k Sorted Lists 合并k个有序链表 Merge k sorted linked lists and return it as one sorted list. Analyze and describe its complexity. Example: Input: [ 1->4->5, 1->3->4, 2->6 ] Output: 1->1->2->3->4->4->5->6 这
剑指Offer之Java算法习题精讲链表与二叉树专项训练

题目一链表题——反转链表根据单链表的头节点head来返回反转后的链表具体题目如下解法 /** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode() {} * ListNode(int val) { this.val = val; } * ListNode(int val, ListNode next) { this.val = val;
JavaScript 参数中的数组展开 [译]

译者注:本文要讲的是ECMAScript 6中的知识点,如果你连ES5都不了解的话.我得说,你已经很落后了.CSS4,HTML6,甚至ES7 ES8都已经开始规划了,赶紧形动起来吧,否则淘汰! 有些时候,我们需要把一个数组展开成多个元素,然后把这些元素作为函数调用的参数.JavaScript中可以使用Function.prototype.apply来实现这种展开操作,但它不能被应用在执行构造函数的情况下.本文解释了什么是展开操作以及如何在使用new运算符的同时进行展开操作. 1.展开(Sprea

C++实现LeetCode(114.将二叉树展开成链表)

[LeetCode] 114. Flatten Binary Tree to Linked List 将二叉树展开成链表

相关推荐

随机推荐