114. Flatten Binary Tree to Linked List
題意了解
還是分為三部分的情況，假設分為root, root.left, root.right,
假設這兩邊都是有序的情況，就是類似與于交換進行值即可的情況，先遞歸處理左邊的節點，然後再對右邊的元素進行同樣的操作
if（root.left!=null）{進行操作}
然後flattern(root.right)
Efficient Without Additional Data StructureRecursively look for the node with no grandchildren and both left and right child in the left sub-tree. Then store node->right in temp and make node->right=node->left. Insert temp in first node NULL on right of node by node=node->right. Repeat until it is converted to linked list.
For Example,
參考連結
題意了解就是
求一個樹的前序周遊，然後連接配接成為一個連結清單即可
還是樹當中經典的三段方法
- 判斷根節點
- 處理左邊的情況(已經是滿足的情況了)遞歸在這個位置進行處理基本情況
- 處理右邊的情況
步驟
- 如果左孩子節點部位空的話，直接調用函數，遞歸處理該種情況
-
交換左右節點的情況（分割為兩個樹）
- 先保留右邊孩子節點tmp
- root.right = root.left
- root.left = null
- 找到root.right的最後一個節點p
- p.right = tmp
- 繼續遞歸調用該函數對root.right進行同樣的處理
整體方法情況
/**
* 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 == NULL || root->left == NULL && root->right == NULL) { return;}
if(root->left!=NULL)
{
flatten(root->left);
//先保持左邊的情況
TreeNode * temp= root->right;
root->right = root->left;
root->left =NULL;
TreeNode * p = root->right;
//來到最後一個節點處，最右的的一個節點，情況下
while(p->right!=NULL)
{
p = p->right;
}
p->right = temp;
}
// flatten(righ)， 上述
注意在這裡面的root 跟上述遞歸處理當中的root 不是一個東西
flatten(root->right);
}
};
遞歸處理左邊的節點情況
一直要找到9那邊的最右節點元素
Java 版
public void flatten(TreeNode root) {
if(root==null||(root.right==null&&root.left==null))
return;
if(root.left!=null){
flatten(root.left);
TreeNode temp = root.right;
root.right = root.left;
root.left = null;
// 在這裡就是完成了一個過程的情況
TreeNode p = root.right;
while(p.right!=null){
p=p.right;
}
//找到最左邊的情況下面如何進行，
p.right= temp;
}
//上圖當中的flatten(right)處的代碼情況， 處理下面的一個情況
這裡面的
flatten(root.right);
}
關鍵是怎樣将 5
(20) My short post order traversal Java solution for share - LeetCode Discuss
解法的解釋說明) LeetCode 114. Flatten Binary Tree to Linked List - YouTube
最好的解法辦法（也是比較好了解的情況）
class Solution {
// public TreeNode pre = null;
public void flatten(TreeNode root) {
if(root==null)
return;
注意在這裡要注意寫法情況，如果是寫成
//if(root.left!=null)
flatten(root.left);
flatten(root.right);
// 如果右邊沒有的話直接傳回
if(root.left==null) return;
TreeNode node= root.left;
while(node.right!=null) node =node.right;
node.right =root.right;
root.right = root.left;
root.left = null;
}
}
解法的解釋說明) LeetCode 114. Flatten Binary Tree to Linked List - YouTube
錯誤的寫法導緻的空指針異常
class Solution {
// public TreeNode pre = null;
public void flatten(TreeNode root) {
if(root==null)
return;
if(root.left!=null) flatten(root.left);
if(root.right!=null) flatten(root.right);
TreeNode node= root.left;
while(node.right!=null) node =node.right;
node.right =root.right;
root.right = root.left;
root.left = null;
}
}
對上述代碼進行改進的話就不會出現空指針異常
class Solution {
// public TreeNode pre = null;
public void flatten(TreeNode root) {
if(root==null)
return;
if(root.left!=null) flatten(root.left);
if(root.right!=null) flatten(root.right);
//加下面的判斷，
if(root.left!=null) return;
TreeNode node= root.left;
while(node.right!=null) node =node.right;
node.right =root.right;
root.right = root.left;
root.left = null;
}
}
[參考連結方法] Flatten Binary Tree to Linked List 将二叉樹展開成連結清單 - Grandyang - 部落格園](http://www.cnblogs.com/grandyang/p/4293853.html)
非遞歸處理方法
public void flatten(TreeNode root) {
if (root == null) return;
Stack<TreeNode> stk = new Stack<TreeNode>();
stk.push(root);
while (!stk.isEmpty()){
TreeNode curr = stk.pop();
if (curr.right!=null)
stk.push(curr.right);
if (curr.left!=null)
stk.push(curr.left);
if (!stk.isEmpty())
curr.right = stk.peek();
curr.left = null; // dont forget this!!
}
}
先讓兩邊的情況都符合情況