題目鏈接：把二叉樹(shù)打印成多行
題目簡(jiǎn)述
從上到下按層打印二叉樹(shù)，同一層結(jié)點(diǎn)從左至右輸出霉撵。每一層輸出一行洪囤。
題解思路
分層打印二叉樹(shù)喊巍，可以預(yù)見(jiàn)到箍鼓，利用BFS搜索的思想即可做到。
題解代碼
/*
struct TreeNode {
int val;
struct TreeNode *left;
struct TreeNode *right;
TreeNode(int x) :
val(x), left(NULL), right(NULL) {
}
};
*/
class Solution {
public:
vector<vector<int> > Print(TreeNode* pRoot) {
vector<vector<int> > vv;
queue<TreeNode*> qu;
vector<int> v;
if(pRoot == NULL) return vv;
qu.push(pRoot);
while(!qu.empty())
{
int qs = qu.size();
while(qs--)
{
v.push_back(qu.front()->val);
if(qu.front()->left != NULL) qu.push(qu.front()->left);
if(qu.front()->right != NULL) qu.push(qu.front()->right);
qu.pop();
}
vv.push_back(v);
v.clear();
}
return vv;
}
};
題目鏈接：按照之字形打印二叉樹(shù)
題目簡(jiǎn)述
請(qǐng)實(shí)現(xiàn)一個(gè)函數(shù)按照之字形打印二叉樹(shù)何暮，即第一行按照從左到右的順序打印铐殃，第二層按照從右至左的順序打印，第三行按照從左到右的順序打印坏逢，其他行以此類推。
題解思路
與上一題類似是整，但是多了一個(gè)在奇數(shù)行(假設(shè)第一行是第零行）反向打印，設(shè)置一個(gè)標(biāo)記flag即可浮入。
題解代碼
/*
struct TreeNode {
int val;
struct TreeNode *left;
struct TreeNode *right;
TreeNode(int x) :
val(x), left(NULL), right(NULL) {
}
};
*/
class Solution {
public:
vector<vector<int> > Print(TreeNode* pRoot) {
vector<vector<int> > vv;
queue<TreeNode*> qu;
vector<int> v;
int f = 0;
if(pRoot == NULL) return vv;
qu.push(pRoot);
while(!qu.empty())
{
int qs = qu.size();
while(qs--)
{
v.push_back(qu.front()->val);
if(qu.front()->left != NULL) qu.push(qu.front()->left);
if(qu.front()->right != NULL) qu.push(qu.front()->right);
qu.pop();
}
f++;
if(f%2 == 0)
{
reverse(v.begin(), v.end());
}
vv.push_back(v);
v.clear();
}
return vv;
}
};
題目鏈接：重建二叉樹(shù)
題目簡(jiǎn)述
輸入某二叉樹(shù)的前序遍歷和中序遍歷的結(jié)果羊异，請(qǐng)重建出該二叉樹(shù)彤断。假設(shè)輸入的前序遍歷和中序遍歷的結(jié)果中都不含重復(fù)的數(shù)字易迹。例如輸入前序遍歷序列{1,2,4,7,3,5,6,8}和中序遍歷序列{4,7,2,1,5,3,8,6}，則重建二叉樹(shù)并返回睹欲。
題解思路
做這道題目，前序遍歷和中序遍歷的關(guān)系一定要清楚句伶，前序遍歷的第一個(gè)點(diǎn)一定是根節(jié)點(diǎn)，然后我們?cè)谥行虮闅v找到根節(jié)點(diǎn)先嬉，則中序遍歷前面是左子樹(shù)楚堤，后面是右子樹(shù)，然后遞歸地進(jìn)行下去身冬。
題解代碼
/**
* Definition for binary tree
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
TreeNode* reConstructBinaryTree(vector<int> pre,vector<int> vin) {
if(pre.size() == 0 || vin.size() == 0) return NULL;
TreeNode* root = new TreeNode(pre[0]);
for(int i=0; i<vin.size(); ++i)
{
if(vin[i] == pre[0])
{
vector<int> a;
vector<int> b;
a.assign(pre.begin()+1, pre.begin()+i+1);
b.assign(vin.begin(), vin.begin()+i);
root->left = reConstructBinaryTree(a, b);
a.clear();
b.clear();
a.assign(pre.begin()+i+1, pre.end());
b.assign(vin.begin()+i+1, vin.end());
root->right = reConstructBinaryTree(a, b);
}
}
return root;
}
};
題目鏈接：二叉樹(shù)的下一個(gè)結(jié)點(diǎn)
題目簡(jiǎn)述
給定一個(gè)二叉樹(shù)和其中的一個(gè)結(jié)點(diǎn)，請(qǐng)找出中序遍歷順序的下一個(gè)結(jié)點(diǎn)并且返回酥筝。注意，樹(shù)中的結(jié)點(diǎn)不僅包含左右子結(jié)點(diǎn)嘿歌，同時(shí)包含指向父結(jié)點(diǎn)的指針。
題解思路
給定的是中序遍歷丧凤，我們拿到了當(dāng)前節(jié)點(diǎn)步脓，想要找到下一個(gè)節(jié)點(diǎn)，這樣有兩個(gè)情況靴患。如果我們有右子樹(shù)，那么下一個(gè)節(jié)點(diǎn)一定在右子樹(shù)中：進(jìn)入右子樹(shù)蚁廓，我們重新中序遍歷，下一個(gè)點(diǎn)一定是最左的葉子節(jié)點(diǎn)相嵌。另一種情況是沒(méi)有右子樹(shù)，那么下一個(gè)節(jié)點(diǎn)一定是他的父親節(jié)點(diǎn)以上批糟，如果當(dāng)前節(jié)點(diǎn)是父親節(jié)點(diǎn)的右節(jié)點(diǎn)，那么要繼續(xù)向上搜索徽鼎，如果是左節(jié)點(diǎn)弹惦，那就是該節(jié)點(diǎn)否淤。
題解代碼
/*
struct TreeLinkNode {
int val;
struct TreeLinkNode *left;
struct TreeLinkNode *right;
struct TreeLinkNode *next;
TreeLinkNode(int x) :val(x), left(NULL), right(NULL), next(NULL) {
}
};
*/
class Solution {
public:
TreeLinkNode* GetNext(TreeLinkNode* pNode)
{
if(pNode == NULL) return NULL;
if(pNode->right != NULL)
{
pNode = pNode->right;
while(pNode->left != NULL) pNode = pNode->left;
return pNode;
}
while(pNode->next != NULL)
{
if(pNode->next->left == pNode)
return pNode->next;
pNode = pNode->next;
}
return NULL;
}
};
題目鏈接：對(duì)稱的二叉樹(shù)
題目簡(jiǎn)述
請(qǐng)實(shí)現(xiàn)一個(gè)函數(shù)石抡，用來(lái)判斷一顆二叉樹(shù)是不是對(duì)稱的。注意助泽，如果一個(gè)二叉樹(shù)同此二叉樹(shù)的鏡像是同樣的，定義其為對(duì)稱的隐解。
題解思路
這道題其實(shí)很簡(jiǎn)單，當(dāng)初做的時(shí)候只是搞錯(cuò)了這個(gè)鏡像的定義煞茫，這個(gè)鏡像只是針對(duì)整個(gè)二叉樹(shù)而言的摄凡，對(duì)于子樹(shù)沒(méi)有要求。
題解代碼
/*
struct TreeNode {
int val;
struct TreeNode *left;
struct TreeNode *right;
TreeNode(int x) :
val(x), left(NULL), right(NULL) {
}
};
*/
class Solution {
public:
bool judge(TreeNode* node1, TreeNode* node2)
{
if(node1 == NULL && node2 == NULL) return true;
if(node1 == NULL || node2 == NULL) return false;
if(node1->val == node2->val)
{
return judge(node1->left, node2->right) && judge(node1->right, node2->left);
}
return false;
}
bool isSymmetrical(TreeNode* pRoot)
{
if(pRoot == NULL) return true;
return judge(pRoot->left, pRoot->right);
}
};
