目錄
一、二叉樹與雙鏈表之間的轉換
（1、解法一
（2、解法二
二、二叉樹與單鏈表之間的轉換
（1、解法一、前序遍歷
（2、解法二、后序遍歷
一、二叉樹與雙鏈表之間的轉換
牛客網鏈接：轉換問題，
對于這種鏈表轉換的題目，都是要通過遍歷來解決問題，
（1、解法一
我們可以專門定義一個函式來將雙鏈表來進行轉換，轉換完成之后我們，轉換完成之后我們找它的頭節點就行了，
public class Solution {
TreeNode cur=null;
public TreeNode Convert(TreeNode pRootOfTree) {
if(pRootOfTree==null) return null;
convertTree(pRootOfTree);
TreeNode temp=pRootOfTree;
while(temp.left!=null){
temp=temp.left;
}
return temp;
}
public void convertTree(TreeNode pCur){
if(pCur==null) return;
convertTree(pCur.left);
pCur.left=cur;
if(cur!=null){
cur.right=pCur;
}
cur=pCur;
convertTree(pCur.right);
}
}（2、解法二
我們可以直接在本函式中進行遍歷，我們定義兩個變數，在函式內部進行定義，
public class Solution {
TreeNode cur=null;
TreeNode pre=null;
public TreeNode Convert(TreeNode pRootOfTree) {
if(pRootOfTree==null) return null;
Convert(pRootOfTree.left);
if(cur==null){
cur=pRootOfTree;
}
if(pre!=null){
pRootOfTree.left=pre;
pre.right=pRootOfTree;
}
pre=pRootOfTree;
Convert(pRootOfTree.right);
return cur;
}
}二、二叉樹與單鏈表之間的轉換
力扣鏈接：題目，
（1、解法一、前序遍歷
class Solution {
public void flatten(TreeNode root) {
if(root==null) return;
if(root.left!=null){
TreeNode temp=root.left;
while(temp.right!=null){
temp=temp.right;
}
temp.right=root.right;
root.right=root.left;
root.left=null;
}
flatten(root.left);
flatten(root.right);
}
}
對于前序遍歷的方法，我們判斷根節點的左子樹是否為空，通過將右子樹接到左子樹的右結點上，再將左子樹接到右子樹上，把左子樹置為空，用遞回不斷的遍歷去做就行了，
（2、解法二、后序遍歷
class Solution {
public void flatten(TreeNode root) {
if(root==null) return;
flatten(root.left);
flatten(root.right);
TreeNode temp=root.right;
root.right=root.left;
root.left=null;
while(root.right!=null){
root=root.right;
}
root.right=temp;
}
}
我們通過后續遍歷一步步還原，將右子樹取出，將左子樹轉換成右子樹，在將原來的右子樹接入，不斷的還原就行了，
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/312123.html
標籤：其他