1. 二叉树的深度

//递归版本（dfs）int treeDepth(TreeNode* root) {if(!root)return 0;int ld=treeDepth(root->left);int rd=treeDepth(root->right);if(ld>rd)return ld+1;else return rd+1;}
//简化：int treeDepth(TreeNode* root) {if(!root)return 0;return max(treeDepth(root->left),treeDepth(root->right))+1;}

//非递归版本（bfs）int maxsize=1e6;int treeDepth(TreeNode* root) {if(!root)return 0;int front=-1,rear=-1;int last=0,level=0;TreeNode* Q[maxsize];Q[++rear]=root;TreeNode* p;while(front<rear){p=Q[++front];if(p->left)Q[++rear]=p->left;if(p->right)Q[++rear]=p->right;if(front==last){level++;last=rear;}}return level;}

2. 判断完全二叉树
   利用层序遍历算法，将所有结点包括空节点都加入队列，遇到空节点时检查其后有无出现非空节点，若有就不是完全二叉树

	bool isCompleted(TreeNode* root) {if(!root)return true;queue<TreeNode*>q;q.push(root);TreeNode*p;while(q.size()){p=q.front();q.pop();if(p){q.push(p->left);q.push(p->right);}else{while(q.size()){p=q.front();q.pop();if(p)return false;}}}return true;}

3. 判断平衡二叉树

	bool res=true;bool isBalanced(TreeNode* root) {dfs(root);return res;}int dfs(TreeNode*root){if(!root)return 0;int ld=dfs(root->left),rd=dfs(root->right);if(abs(ld-rd)>1)res=false;return max(ld,rd)+1;}

4. 树中两结点的最近祖先
   递归思路：①结点p，q位于不同的子树上，及这不同的两棵树的根结点即为两者最近祖先②位于同一棵子树上，若p在前就为p，反之为q

	TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {if(!root)return NULL;if(root==p||root==q)return root;auto left=lowestCommonAncestor(root->left,p,q);auto right=lowestCommonAncestor(root->right,p,q);if(left&&right)return root;if(left)return left;return right;}