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

題目大意：

將一個二叉樹變為一個鏈表

解法：

這道題目輸出結果就是采用前序遍歷二叉樹的結果，將這個結果變為一個雙向鏈表。但是題目的要求是在原數據結構上進行改變，而不是采用前序遍歷的結果新建一個鏈表。這道題目劍指offer上面也有，做過很多次，但是記不得，最討厭做樹相關的題目了。

參考了一下網上的解法，看起來還是很容易理解的，就是將左右子樹遞歸的變成鏈表，再和當前節點相連接。但是感覺自己很難想出來。

解法主要是下面三步：

1.將左子樹轉換成鏈表

2.將右子樹轉換成鏈表

3.將當前節點的左指針指向空，右節點指向leftList.head，然后將leftList.end指向rightList.head。

java:

class Solution {public void flatten(TreeNode root) {if(root==null) return;TreeNode left=root.left;TreeNode right=root.right;flatten(left);flatten(right);root.left=null;root.right=left;TreeNode cur=root;while(cur.right!=null) cur=cur.right;cur.right=right;} }

?

轉載于:https://www.cnblogs.com/xiaobaituyun/p/10705707.html

總結

以上是生活随笔為你收集整理的leetcode [114]Flatten Binary Tree to Linked List的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。