二叉树（重建、层序、深度、平衡二叉树）

 

/** * Definition for binary tree * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */

 

 

 

 

 

1.重建二叉树（前序、中序）

 

TreeNode* reConstructBinaryTree(vector<int> pre,vector<int> vin) { int n1 = pre.size(); int n2 = vin.size(); if(n1 != n2 || n1 <= 0) { return NULL; } TreeNode *root = new TreeNode(pre[0]); int pos = 0; for(;pos<n2;++pos) { if(vin[pos] == pre[0]) break; } if(pos == n2) exit(-1); vector<int> pre_left,vin_left,pre_right,vin_right; for(int i=0;i < n1;++i) { if(i<pos) { pre_left.push_back(pre[i+1]); vin_left.push_back(vin[i]); } else if(i>pos) { pre_right.push_back(pre[i]); vin_right.push_back(vin[i]); } } root->left = reConstructBinaryTree(pre_left,vin_left); root->right = reConstructBinaryTree(pre_right,vin_right); return root; } { if(vin[pos] == pre[0]) break; } if(pos == n2) exit(-1); vector<int> pre_left,vin_left,pre_right,vin_right; for(int i=0;i < n1;++i) { if(i<pos) { pre_left.push_back(pre[i+1]); vin_left.push_back(vin[i]); } else if(i>pos) { pre_right.push_back(pre[i]); vin_right.push_back(vin[i]); } } root->left = reConstructBinaryTree(pre_left,vin_left); root->right = reConstructBinaryTree(pre_right,vin_right); return root; }

中序、后序重建二叉树，与前序、中序重建二叉树思想一致。利用前序或者后序遍历根结点的位置特性，找到中序遍历序列中根结点的位置，进而将中序遍历序、前序或者后序列分成左子树、根结点、右子树，左右子树进行递归。

 

先序、后序无法重建二叉树。

2.层序遍历二叉树

 

vector<int> PrintFromTopToBottom(TreeNode* root) { vector<TreeNode *> tree; vector<int> res; if(root == NULL) return res; tree.push_back(root); TreeNode *pnode = NULL; while(tree.size()) { pnode = tree.front(); tree.erase(tree.begin()); res.push_back(pnode->val); if(pnode->left) tree.push_back(pnode->left); if(pnode->right) tree.push_back(pnode->right); } return res; } };

利用队列先进先出的思想，首先将根结点入进去，出一个结点，如果左/右子树不为NULL，将它的左/右子节点入进去。

 

3.二叉树的深度

 

int TreeDepth(TreeNode* pRoot) { if(pRoot == NULL) return 0; else { int left_depth = TreeDepth(pRoot->left); int rigth_depth = TreeDepth(pRoot->right); return left_depth > rigth_depth ? left_depth +1 : rigth_depth+1; } }

利用递归的思想，二叉树的深度为左右子树深度最大值+1。

 

4.二叉树是否是平衡二叉树

 

//一个节点被重复遍历多次 int TreeDepth(TreeNode* pRoot) { if(pRoot == NULL) return 0; else { int left_depth = TreeDepth(pRoot->left); int rigth_depth = TreeDepth(pRoot->right); return left_depth > rigth_depth ? left_depth +1 : rigth_depth+1; } } bool IsBalanced_Solution(TreeNode* pRoot) { return (pRoot == NULL) || ( abs(TreeDepth(pRoot->left)-TreeDepth(pRoot->right)) <= 1 && IsBalanced_Solution(pRoot->left) && IsBalanced_Solution(pRoot->right) ); }

结合求深度的方法，对二叉树进行递归判断，优点是思想容易理解，代码简洁。缺点是一个节点被重复遍历多次。

 

改进：一遍进行后序遍历，一边进行判断。此时每个结点只遍历一次。

 

bool IsBalanced(TreeNode *root, int & dep){ if(root == NULL){ return true; } int left = 0; int right = 0; if(IsBalanced(root->left,left) && IsBalanced(root->right, right)){ int dif = left - right; if(dif<-1 || dif >1) return false; dep = (left > right ? left : right) + 1; return true; } return false; } bool IsBalanced_Solution(TreeNode* pRoot) { int dep = 0; return IsBalanced(pRoot, dep); }