二叉树面试题

二叉树的定义

struct TreeNode
{
    int val;
    TreeNode *left,*right;
    TreeNode(int x):val(x),left(0),right(0){}
};

1.求二叉树的结点个数

int f(TreeNode *root)
{
    if(!root)return 0;
    return f(root->left)+f(root->right)+1;
}

2.求二叉树的深度

int f(TreeNode *root)
{
    if(!root)return 0;
    return max(f(root->left),f(root->right))+1;
}

3.前、中、后序遍历

void preorderTraversal(TreeNode *root)  
{  
    if(root)  
    {  
        cout<<root->val<<' ';
        preorderTraversal(root->left);  
        preorderTraversal(root->right);   
    }   
}  

void inorderTraversal(TreeNode *root)  
{  
    if(root)  
    {  
        inorderTraversal(root->left);
        cout<<root->val<<' ';
        inorderTraversal(root->right);   
    }   
}

void postorderTraversal(TreeNode *root)
{
    if(root)
    {
        postorderTraversal(root->left);
        postorderTraversal(root->right);
        cout<<root->val<<' ';
    }
}

http://blog.csdn.net/hz5034/article/details/45582493

http://blog.csdn.net/hz5034/article/details/45599957

4.层序遍历

void levelorderTraverse(TreeNode *root)  
{
 if(!root)return;   
 queue<TreeNode *> q;
 q.push(root);
 TreeNode *p;
 while(!q.empty())  
 {  
  p=q.front();  
  q.pop();  
  cout<<p->val<<' ';  
  if(!p->left)q.push(p->left);  
  if(!p->right)q.push(p->right);  
 }  
}

http://blog.csdn.net/hz5034/article/details/44275239

5.重建二叉树

//前序+中序
TreeNode *rebuild(int pre[],int in[],int n)
{
 if(n==0)return 0;
 TreeNode *root=new TreeNode(pre[0]);
 int i;
 for(i=0;i<n;++i)
 {
  if(in[i]==root->val)break;
 }
 //重建左子树
 root->left=rebuild(pre+1,in,i);
 //重建右子树
 root->right=rebuild(pre+i+1,in+i+1,n-i-1);
 return root;
}

//中序+后序
TreeNode *rebuild(int in[],int post[],int n)
{
 if(n==0)return 0;
 TreeNode *root=new TreeNode(post[n-1]);
 int i;
 for(i=0;i<n;++i)
 {
  if(in[i]==root->val)break;
 }
 //重建左子树
 root->left=rebuild(in,post,i);
 //重建右子树
 root->right=rebuild(in+i+1,post+i,n-i-1);   
 return root;
}

6.求二叉树中节点的最大距离

struct result
{
 int maxDistance;
 int maxDepth;
};

result f(TreeNode *root)
{
 if(!root)
 {
  result r={0,-1};
  return r;
 }
 result left=f(root->left);
 result right=f(root->right);
 result r;
 r.maxDistance=max(max(left.maxDistance,right.maxDistance),left.maxDepth+right.maxDepth+1);
 r.maxDepth=max(left.maxDepth,right.maxDepth)+1;
 return r;
}

http://www.cnblogs.com/miloyip/archive/2010/02/25/1673114.html

7.二叉树中和为某一值的路径

深搜一：

class Solution {
public:
     vector<vector<int>> pathSum(TreeNode* root, int sum) {
  vector<vector<int> > result;
  vector<int> path;
  dfs(root,sum,result,path);
  return result;
 }
 void dfs(TreeNode *root,int sum,vector<vector<int> > &result,vector<int> &path)
 {
  if(!root)return;
  path.push_back(root->val);
  if(!root->left&&!root->right&&sum==root->val)result.push_back(path);
  dfs(root->left,sum-root->val,result,path);
  dfs(root->right,sum-root->val,result,path);
  path.pop_back();
 }
};

深搜二：

class Solution {
public:
        vector<vector<int>> pathSum(TreeNode* root, int sum) {
  vector<vector<int> > result;
  vector<int> path;
  int s=0;
  dfs(root,sum,result,path,s);
  return result;
 }
 void dfs(TreeNode *root,int sum,vector<vector<int> > &result,vector<int> &path,int &s)    
 {
  if(!root)return;
  path.push_back(root->val);
  s+=root->val;
  if(!root->left&&!root->right&&s==sum)result.push_back(path);
  dfs(root->left,sum,result,path,s);
  dfs(root->right,sum,result,path,s);
  s-=path.back();
  path.pop_back();
 }
};