103. Binary Tree Zigzag Level Order Traversal
题目
分析：
广度优先遍历的应用。重点是掌握vector的reverse函数，一开始我忘记有这个函数了，琢磨半天都没弄出来，后来想起reverse函数，问题一下子就迎刃而解。
代码
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
vector<vector<int>> zigzagLevelOrder(TreeNode* root) {
vector<vector<int>> res;
vector<int> temp;
if(NULL == root)
return res; queue<TreeNode*> myQue;
TreeNode *temp1;
bool flag = true;
myQue.push(root); while (!myQue.empty())
{
temp.clear();
myQue.push(NULL);
temp1 = myQue.front();
myQue.pop();
while (NULL != temp1)
{
temp.push_back(temp1->val);
if(NULL != temp1->left)
myQue.push(temp1->left);
if(NULL != temp1->right)
myQue.push(temp1->right);
temp1 = myQue.front();
myQue.pop();
}
if(!flag)
{
reverse(temp.begin(),temp.end());
} res.push_back(temp);
flag = (!flag);
}
} };
---------------------------------------------------------------------------------------分割线-------------------------------------------------------------------------
104. Maximum Depth of Binary Tree
题目
分析：
求树的深度，递归。代码如下：
/**
* Definition for binary tree
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
int maxDepth(TreeNode *root) {
if(NULL == root)return ;
int min1=;
int min2=;
min1 = maxDepth(root->left);
min2 = maxDepth(root->right); return (min1>min2 ? min1:min2)+; }
};
----------------------------------------------------------------------------------------分割线----------------------------------------------------------------------------------
105. Construct Binary Tree from Preorder and Inorder Traversal
题目;
分析：
题目要求利用前序、中序遍历构造一棵二叉树。
基本思想：通过前序遍历数组，找到当前子树的根节点在中序遍历数组中的下标，然后将中序遍历数组一分为二，一部分为左子树，一部分为右子树。递归调用构造完整的二叉树。
其中存在特殊情况，某个节点没有左子树，或者没有右子树，或者左右子树都不存在。
代码如下
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
int size = preorder.size();
if( == size)
return NULL;
//TreeNode *root = myBuild(preorder,inorder,0,0,size-1);这里不能直接传0，因为参数是引用
int index = ;
TreeNode *root = myBuild(preorder,inorder,index,,size-);
}
TreeNode* myBuild(vector<int>& preorder, vector<int>& inorder,int& index,int start,int end)//index为什么要用引用
{
//if(start == end)
//{
// return new TreeNode(inorder[start]);
//}
int i=start;
//for(;i<inorder.size();i++)
for(;i<=end;i++)
{
if(inorder[i] == preorder[index])
break;
} TreeNode *temp = new TreeNode(preorder[index]);
if(i == start)//当前节点没有左子树
temp->left = NULL;
else
temp->left = myBuild(preorder,inorder,++index,start,i-);
if(i == end)//当前节点没有右子树
temp->right = NULL;
else
temp->right = myBuild(preorder,inorder,++index,i+,end); return temp;
}
};
----------------------------------------------------------------------------分割线----------------------------------------------------------------
106. Construct Binary Tree from Inorder and Postorder Traversal
题目
分析：
通过二叉树的中序遍历和后序遍历来构造二叉树。
基本思想：通过后序遍历数组，找到当前子树的根节点在中序遍历数组中的下标，然后将中序遍历数组一分为二，一部分为左子树，一部分为右子树。递归调用构造完整的二叉树。
比较105和106题。可以发现，中序遍历数组在整个构造二叉树过程中起着"分岭"作用，如果只有前序和后序遍历，构造二叉树就比较麻烦了。
需要了解的是后序遍历数组中，最后一个节点就是当前子树的根节点，所以代码实现是从后序遍历数组的尾部开始，从后往前的遍历。
代码如下：
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {
int size = postorder.size();
if( == size)
return NULL;
TreeNode *root = myBuild(inorder,postorder,,size-,size-);
}
//函数每次从postorder的尾部开始遍历，也就是从后往前遍历，参数index是指向当前需要访问postorder中的最后一个元素
TreeNode* myBuild(vector<int>& inorder, vector<int>& postorder,int start,int end,int index)//start,length是用于inorder数组中的,
{
//if(start == end)
//{
// return new TreeNode(inorder[start]);
//}
int i=start;
//for(;i<inorder.size();i++)
for(;i<=end;i++)
{
if(inorder[i] == postorder[index])
break;
}
//找到i下标，将inorder分为两部分，一部分是左子树，一部分是右子树
TreeNode *temp = new TreeNode(postorder[index]);
if(i == start)//当前节点没有左子树
temp->left = NULL;
else
temp->left = myBuild(inorder,postorder,start,i-,index-(end-i)-);//index-(end-i)-1是左子树的根节点在postorder中的下标
if(i == end)//当前节点没有右子树
temp->right = NULL;
else
temp->right = myBuild(inorder,postorder,i+,end,index-);//index-1是右子树的根节点在postorder中的下标 return temp;
}
};