題目描述
輸入一棵二叉搜索樹，將該二叉搜索樹轉換成一個排序的雙向鏈表，要求不能創建任何新的結點，只能調整樹中結點指標的指向，
牛客網鏈接
js代碼
/* function TreeNode(x) {
this.val = x;
this.left = null;
this.right = null;
} */
//方法一
let queue = []
function Convert(pRootOfTree)
{
// write code here
if (!pRootOfTree) return null
if (!pRootOfTree.left && !pRootOfTree.right) return pRootOfTree
ConvertHelp(pRootOfTree)
let head = queue.shift()
let pre = head
let now
while (queue.length !== 0){
now = queue.shift()
now.left = pre
pre.right = now
pre = now
}
head.left = null
now.right = null
return head
}
function ConvertHelp(pRootOfTree) {
if (!pRootOfTree) return
ConvertHelp(pRootOfTree.left)
queue.push(pRootOfTree)
ConvertHelp(pRootOfTree.right)
}
//方法二
function Convert(pRootOfTree)
{
// write code here
if (!pRootOfTree) return null
let pre = null
ConvertHelp(pRootOfTree)
while (pRootOfTree.left) {
pRootOfTree = pRootOfTree.left
}
return pRootOfTree
function ConvertHelp(cur) {
if (!cur) return
if (cur.left) pre = ConvertHelp(cur.left)
cur.left = pre
if (pre) pre.right = cur
pre = cur
if (cur.right) pre = ConvertHelp(cur.right)
return pre
}
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/138800.html
標籤：其他
上一篇：排序演算法小匯總