生活随笔
收集整理的這篇文章主要介紹了
LeetCode 919. 完全二叉树插入器（层序遍历队列）
小編覺得挺不錯的,現(xiàn)在分享給大家,幫大家做個參考.
1. 題目
完全二叉樹是每一層（除最后一層外）都是完全填充（即，結(jié)點數(shù)達(dá)到最大）的，并且所有的結(jié)點都盡可能地集中在左側(cè)。
設(shè)計一個用完全二叉樹初始化的數(shù)據(jù)結(jié)構(gòu) CBTInserter，它支持以下幾種操作：
- CBTInserter(TreeNode root) 使用頭結(jié)點為 root 的給定樹初始化該數(shù)據(jù)結(jié)構(gòu)；
- CBTInserter.insert(int v) 將 TreeNode 插入到存在值為 node.val = v 的樹中以使其保持完全二叉樹的狀態(tài)，并返回插入的 TreeNode 的父結(jié)點的值；
- CBTInserter.get_root() 將返回樹的頭結(jié)點。
示例
1：
輸入：inputs
= ["CBTInserter","insert","get_root"],
inputs
= [[[1]],[2],[]]
輸出：
[null
,1,[1,2]]示例
2：
輸入：inputs
= ["CBTInserter","insert","insert","get_root"],
inputs
= [[[1,2,3,4,5,6]],[7],[8],[]]
輸出：
[null
,3,4,[1,2,3,4,5,6,7,8]]提示：
最初給定的樹是完全二叉樹，且包含
1 到
1000 個結(jié)點。
每個測試用例最多調(diào)用 CBTInserter
.insert 操作
10000 次。
給定結(jié)點或插入結(jié)點的每個值都在
0 到
5000 之間。
來源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/complete-binary-tree-inserter
著作權(quán)歸領(lǐng)扣網(wǎng)絡(luò)所有。商業(yè)轉(zhuǎn)載請聯(lián)系官方授權(quán)，非商業(yè)轉(zhuǎn)載請注明出處。
2. 解題
- 先按層序將樹的節(jié)點放進(jìn)數(shù)組，并將節(jié)點之間的連接關(guān)系拆開
- 用一個隊列存儲完全二叉樹中的節(jié)點（其子節(jié)點沒插滿的節(jié)點）
class CBTInserter {TreeNode
*r
= NULL;vector
<TreeNode
*> insertNode
;int i
, fatherVal
;queue
<TreeNode
*> upperLv
;TreeNode
*tp
;
public:CBTInserter(TreeNode
* root
) {lvOrder(root
);if(r
== NULL){r
= insertNode
.front();insertNode
.erase(insertNode
.begin());upperLv
.push(r
);}while(!insertNode
.empty()){tp
= insertNode
.front();insertNode
.erase(insertNode
.begin());upperLv
.push(tp
);if(upperLv
.front()->left
== NULL)upperLv
.front()->left
= tp
;else{upperLv
.front()->right
= tp
;upperLv
.pop();}}}int insert(int v
) {fatherVal
= upperLv
.front()->val
;tp
= new TreeNode(v
);if(upperLv
.front()->left
== NULL)upperLv
.front()->left
= tp
;else{upperLv
.front()->right
= tp
;upperLv
.pop();}upperLv
.push(tp
);return fatherVal
;}TreeNode
* get_root() {return r
;}void lvOrder(TreeNode
*root
){if(root
== NULL)return;insertNode
.clear();insertNode
.push_back(root
);for(i
= 0; i
< insertNode
.size(); ++i
){if(insertNode
[i
]->left
)insertNode
.push_back(insertNode
[i
]->left
);if(insertNode
[i
]->right
)insertNode
.push_back(insertNode
[i
]->right
);insertNode
[i
]->left
= insertNode
[i
]->right
= NULL;}}
};
創(chuàng)作挑戰(zhàn)賽新人創(chuàng)作獎勵來咯，堅持創(chuàng)作打卡瓜分現(xiàn)金大獎
總結(jié)
以上是生活随笔為你收集整理的LeetCode 919. 完全二叉树插入器（层序遍历队列）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。
如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。
