题目如下:
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
初看这道题觉得很简单,就是一个dfs,上手写起来后才发现没那么容易,这道题要求直接对原二叉树进行修改,开List遍历二叉树再将List中的节点连接的办法没能AC,看了讨论区以后发现下面这个解法比较容易理解。
/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */ class Solution { public static void flatten(TreeNode root) { if (root == null) { return; } TreeNode left = root.left; TreeNode right = root.right; root.left = null; flatten(left); flatten(right); root.right = left; TreeNode node = root; while (node.right != null) { node = node.right; } node.right = right; return; } }
- 本文固定链接: https://weiguangli.com/archives/418
- 转载请注明: lwg0452 于 Weiguang的博客 发表
捐 赠如果您觉得这篇文章有用处,请支持作者!鼓励作者写出更好更多的文章!