前言
今天的題目
每天的題目見github(看最新的日期):
https://github.com/gzc426
具體的題目可以去牛客網(wǎng)對應(yīng)專題去找。
昨天的題解
題目
每天一道劍指offer-二叉搜索樹與雙向鏈表
來源：
https://www.nowcoder.com/practice/947f6eb80d944a84850b0538bf0ec3a5?tpId=13&tqId=11179&tPage=2&rp=2&ru=/ta/coding-interviews&qru=/ta/coding-interviews/question-ranking
題目詳述
輸入一棵二叉搜索樹，將該二叉搜索樹轉(zhuǎn)換成一個排序的雙向鏈表。要求不能創(chuàng)建任何新的結(jié)點，只能調(diào)整樹中結(jié)點指針的指向。
題目詳解
思路
先中序遍歷二叉搜索樹，這樣二叉搜索樹就按照val值的大小從小到大排好序了，存放在數(shù)組中
然后要轉(zhuǎn)換為雙向鏈表，由于數(shù)組中的存放的樹的節(jié)點已經(jīng)按照鍵值從小到大排好序了，那么就對于每個節(jié)點的左子樹指向數(shù)組的上一個節(jié)點，右子樹指向數(shù)組的下一個節(jié)點，這樣就完成了變成雙向鏈表。
代碼
public class Solution {
? ?public TreeNode Convert(TreeNode pRootOfTree) {
? ? ? ?if(pRootOfTree == null || (pRootOfTree.left == null && pRootOfTree.right == null))
? ? ? ? ? ?return pRootOfTree;
? ? ? ?ArrayList<TreeNode> nodeList = new ArrayList<>();
? ? ? ?BuildArrayList(pRootOfTree,nodeList);//這個函數(shù)執(zhí)行后，數(shù)組中每個元素按照大小前后排序
? ? ? ?for(int i=0;i<nodeList.size();i++)
? ? ? ?{
? ? ? ? ? ?if(i == 0)
? ? ? ? ? ?{//數(shù)組的第一個節(jié)點處理，只有右子樹指向下一個節(jié)點
? ? ? ? ? ? ? ?nodeList.get(0).right = nodeList.get(1);
? ? ? ? ? ?}
? ? ? ? ? ?else if(i == nodeList.size()-1)
? ? ? ? ? ?{//數(shù)組的最后一個節(jié)點，只有左子樹指向前一個節(jié)點
? ? ? ? ? ? ? ?nodeList.get(i).left = nodeList.get(i-1);
? ? ? ? ? ?}
? ? ? ? ? ?else{//數(shù)組中的中間節(jié)點，左子樹指向上一個節(jié)點，右子樹指向數(shù)組的下一個節(jié)點
? ? ? ? ? ? ? ?nodeList.get(i).left = nodeList.get(i-1);
? ? ? ? ? ? ? ?nodeList.get(i).right = nodeList.get(i+1);
? ? ? ? ? ?}
? ? ? ?}
? ? ? ?return nodeList.get(0);
? ?}
? ?public void BuildArrayList(TreeNode root,ArrayList<TreeNode> nodeList)
? ?{//二叉搜索的中序遍歷，并把每個節(jié)點存入數(shù)組中
? ? ? ?if(root == null)
? ? ? ? ? ?return;
? ? ? ?if(root.left != null)//左子樹
? ? ? ? ? ?BuildArrayList(root.left,nodeList);
? ? ? ?if(root != null)//根節(jié)點
? ? ? ? ? ?nodeList.add(root);
? ? ? ?if(root.right != null)//右子樹
? ? ? ? ? ?BuildArrayList(root.right,nodeList);
? ?}
}
代碼截圖（避免亂碼）
結(jié)束語
作者喬戈里親歷2019秋招，哈工大計算機本碩，百度java工程師，歡迎大家關(guān)注我的微信公眾號：程序員喬戈里，公眾號有3T編程資源，以及我和我朋友（百度C++工程師）在秋招期間整理的近200M的面試必考的java與C++面經(jīng)，并有每天一道leetcode打卡群與技術(shù)交流群，歡迎關(guān)注。
