目錄
- 題目詳情
- 一、解題思路
- 二、使用步驟
- 三、代碼
- 總結
題目詳情
題目詳情鏈接
一、解題思路
將原樹進行中序遍歷將樹中的節點的非空值放入到一個list集合中，創建一棵新樹然后通過遞回的方式將不斷生成的新的右子樹直到集合遍歷完，
二、使用步驟
1.對原樹進行中序遍歷，將非空樹的值一次放入到List集合中，
2.創建一個函式用于對集合進行遍歷，將每次遍歷得到的值用來創建當前樹的值，
在集合遍歷完之前，繼續遞回該函式，將傳遞的實參改為當前樹的右子樹，
三、代碼
class Solution {
public TreeNode increasingBST(TreeNode root) {
if(root!=null){
ArrayList array=new ArrayList<>();
Solution s=new Solution();
s.inOrderTraversal(root,array);
root=s.toTree(null,array,0);
return root;
}else{
return null;
}
}
//通過遞回的方式不斷將集合中的值有做新的右子樹的值
public TreeNode toTree(TreeNode root,List<Integer> array,int length){
root=new TreeNode(array.get(length));
root.left=null;
if(length<array.size()-1){
length++;
root.right=toTree(root.right,array,length);
}
return root;
}
//中序遍歷
public void inOrderTraversal(TreeNode root,List<Integer> array){
if(root==null){
return ;
}else{
inOrderTraversal(root.left,array);
array.add(root.val);
inOrderTraversal(root.right,array);
}
}
}
總結
在我看來樹的重點需要掌握的就是樹的遍歷方式，前序、中序、后序、層序，基本上許多和樹有關的題目都會涉及到他的遍歷方式，這些方式都可以通過遞回的方式來實作，
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/244586.html
標籤：其他