【LeetCode101-110】二叉树对称及存储，前序中序遍历生成二叉树，中序后序生成二叉树，数组转化为AVL平衡树，判断二叉树是否平衡
2017-04-24 09:53:41         来源：朱铭德的博客

# 101.二叉树是否对称【easy】

Given a binary tree, check whether it is a mirror of itself (ie, symmetric around its center).

For example, this binary tree`[1,2,2,3,4,4,3]is symmetric:`

``````    1
/ \
2   2
/ \ / \
3  4 4  3
``````

`But the following[1,2,2,null,3,null,3]is not:`

``````    1
/ \
2   2
\   \
3    3``````

`和100题思路一样，通过迭代来判断左右两个自树是否对称……`

``````/**
* 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:
bool isSymmetric(TreeNode* root) {
if(!root)return true;
if(help(root->left,root->right))return true;
return false;
}
bool help(TreeNode*left,TreeNode*right){
if(!left&&right||left&&!right)return false;
if(!left&&!right)return true;
if(!help(left->left,right->right))return false;
if(left->val!=right->val)return false;
if(!help(left->right,right->left))return false;
return true;
}
};``````

# `102.按层级存储二叉树【medium】`

`Given a binary tree, return thelevel ordertraversal of its nodes' values. (ie, from left to right, level by level).`

```For example: Given binary tree[3,9,20,null,null,15,7],```

``````    3
/ \
9  20
/  \
15   7
``````

`return its level order traversal as:`

``````[
[3],
[9,20],
[15,7]
]``````

`还是一样的思路，构造一个函数不断迭代……一个变量判断应该存储再哪一行…`

``````/**
* 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> levelOrder(TreeNode* root) {
vector>result;
help(result,root,0);
return result;
}
void help(vector>&result,TreeNode*root,int level){
if(!root)return;
if(root){
vectortemp;
if(level+1>result.size()){
temp.push_back(root->val);
result.push_back(temp);
}
else result[level].push_back(root->val);
}
help(result,root->left,level+1);
help(result,root->right,level+1);
return;
}
};``````

# `103.按层存储二叉树，偶数层逆序`

`就在上一题的基础之上把偶数层逆序就好了……`

``````/**
* 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> zigzagLevelOrder(TreeNode* root) {
vector>result;
help(result,root,0);
for(int i=1;i>&result,TreeNode*root,int level){
if(!root)return;
if(root){
vectortemp;
if(level+1>result.size()){
temp.push_back(root->val);
result.push_back(temp);
}
else result[level].push_back(root->val);
}
help(result,root->left,level+1);
help(result,root->right,level+1);
return;
}
};``````

# `104.返回二叉树最长长度【easy】`

`迭代下就好了……`

``````class Solution {
public:
int maxDepth(TreeNode* root) {
if(!root)return 0;
if(!root->right&&!root->left)return 1;
return max(maxDepth(root->left),maxDepth(root->right))+1;
}
};``````

# `105.前序遍历&中序遍历生成二叉树`

`前序遍历NLR preorder 根左右`

`中序遍历LNR inorder 左根右`

`后续遍历LRN postorder 左右根`

``````class Solution {
public:
TreeNode* buildTree(vector& preorder, vector& inorder) {
//根据前序以及中序确定一个二叉树
if (preorder.size() == 0)return nullptr;
TreeNode *temp = new TreeNode(preorder[0]);

int length = find(inorder.begin(), inorder.end(), preorder[0]) - inorder.begin();

if (length>0) {
vectorpreorder2(preorder.begin() + 1, preorder.begin() + 1 + length);
vectorinorder2(inorder.begin(), inorder.begin() + length);
temp->left = buildTree(preorder2, inorder2);
}

if (preorder.end() - preorder.begin() - 1 - length>0) {
vectorpreorder3(preorder.begin() + 1 + length, preorder.end());
vectorinorder3(inorder.begin() + length+1 , inorder.end());
temp->right = buildTree(preorder3, inorder3);
}

return temp;
}
};``````

# `106.中序遍历&后序遍历生成二叉树`

`上面的稍微改一下就好了……`

``````class Solution {
public:
TreeNode* buildTree(vector& inorder, vector& postorder) {
//根据中序和后序确定二叉树
//中序：左根右      后序：左右根
if (postorder.size() == 0)return nullptr;
TreeNode *temp = new TreeNode(postorder.back());

int length = find(inorder.begin(), inorder.end(),postorder.back()) - inorder.begin();

if (length>0) {
vectorpostorder2(postorder.begin(), postorder.begin() + length);
vectorinorder2(inorder.begin(), inorder.begin() + length);
temp->left = buildTree( inorder2,postorder2);
}

if (postorder.end() - postorder.begin() - 1 - length>0) {
vectorpostorder3(postorder.begin()  + length, postorder.end()-1);
vectorinorder3(inorder.begin() + length+1 , inorder.end());
temp->right = buildTree( inorder3,postorder3);
}

return temp;
}
}; ``````

# `107.二叉树按级存储（逆序）`

`在102的基础上加一行reverse就好了……`

``````class Solution {
public:
vector> levelOrderBottom(TreeNode* root) {
vector>result;
help(result,root,0);
reverse(result.begin(),result.end());
return result;
}
void help(vector>&result,TreeNode* root,int level){
if(!root)return;
if(root){
if(level+1>result.size()){
vectortemp;
temp.push_back(root->val);
result.push_back(temp);
}
else result[level].push_back(root->val);
}
help(result,root->left,level+1);
help(result,root->right,level+1);
return;
}
};``````

# `108.有序数组转化为AVL树【easy】`

`Given an array where elements are sorted in ascending order, convert it to a height balanced BST.`

`一开始的代码结果是这样的（32/32....)`

`代码是这样的：`

``````/**
* 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* sortedArrayToBST(vector& nums) {
if (nums.size() == 0)return nullptr;
vectortemp;
for (int i = 0; i&temp, int rounds, int max) {
int begin = pow(2, rounds) - 1; int end = pow(2, rounds + 1) - 2;
if (2 * begin + 1 > max)return;
for (int i = begin; i <= end; ++i) {
if (2 * i + 1 <= max)temp[i]->left = temp[2 * i + 1];
else break;
if (2 * i + 2 <= max)temp[i]->right = temp[2 * i + 2];
else break;
}
help(temp, rounds + 1, max);
}

void help2(TreeNode* temp, vectornums, int &i) {
if (!temp)return;
help2(temp->left, nums, i);
temp->val = nums[i];
++i;
help2(temp->right, nums, i);
}
};``````

`然后转换了下思路……发现用Vector太耗费空间了，所有直接迭代就好了……很简洁`

``````/**
* 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* sortedArrayToBST(vector& nums) {
return sortedArrayToBST(nums,0,nums.size());
}
TreeNode* sortedArrayToBST(vector& nums,int begin,int size) {
if(size<=0)return nullptr;
TreeNode *temp=new TreeNode(nums[begin+size/2]);
temp->left=sortedArrayToBST(nums,begin,size/2);
temp->right=sortedArrayToBST(nums,begin+size/2+1,(size+1)/2-1);
return temp;
}
};``````

# `109.单链表转化为AVL树`

`把链表转化为vector，和上一题一样了…，需要O(n)空间…`

``````class Solution {
public:
TreeNode* sortedListToBST(ListNode* head) {
//先试试转化为vector会不会超空间……
vectortemp;
}
return sortedArrayToBST(temp,0,temp.size());
}
TreeNode* sortedArrayToBST(vector& nums,int begin,int size) {
if(size<=0)return nullptr;
TreeNode *temp=new TreeNode(nums[begin+size/2]);
temp->left=sortedArrayToBST(nums,begin,size/2);
temp->right=sortedArrayToBST(nums,begin+size/2+1,(size+1)/2-1);
return temp;
}
};``````

`别人的O(1)空间的方法，关键是中序遍历！！！`
``````class Solution {
public:
ListNode *list;
int count(ListNode *node){
int size = 0;
while (node) {
++size;
node = node->next;
}
return size;
}

TreeNode *generate(int n){
if (n == 0)
return NULL;
TreeNode *node = new TreeNode(0);
node->left = generate(n / 2);
node->val = list->val;
list = list->next;
node->right = generate(n - n / 2 - 1);
return node;
}

TreeNode *sortedListToBST(ListNode *head) {
}
};``````

# `110.判断二叉树是否是平衡的（所有左右子树长度差不超过1）`

`我的方法：（写的时候就觉得其中有很多冗余，但是通过了……O(n2)`

`因为每次都要调用一个深度函数length()`

``````class Solution {
public:
bool isBalanced(TreeNode* root) {
if(!root)return true;
if(abs(length(root->left)-length(root->right))<=1&&isBalanced(root->left)&&isBalanced(root->right))return true;
return false;
}
int length(TreeNode* root){
if(!root)return 0;
if(!root->left&&!root->right)return 1;
return max(length(root->left),length(root->right))+1;
}
};``````
`但其实只要有一个子树不满足，整个就不满足了，所有完全可以在深度函数里有所表示 `

`下面就是参考别人的O(n)的方法//DFS,深度优先的搜索……`

``````class Solution {
public:
int dfsHeight (TreeNode *root) {
if (root == NULL) return 0;

int leftHeight = dfsHeight (root -> left);
if (leftHeight == -1) return -1;
int rightHeight = dfsHeight (root -> right);
if (rightHeight == -1) return -1;

if (abs(leftHeight - rightHeight) > 1)  return -1;
return max (leftHeight, rightHeight) + 1;
}
bool isBalanced(TreeNode *root) {
return dfsHeight (root) != -1;
}
};``````