二叉树应用_二叉树深度-蒲公英云

二叉树应用_二叉树深度

题目：输入一颗二叉树的根节点，求该树的深度。
分析：方法一：在二叉树中和为某一值的路径中已经知道了如何存取树的一条路径，这里我们可以用此方法求出树的最长路径，也就是树的深度。方法二：树的深度即是左、右子树中深度较大的值加1，可以采用此方法进行递归。
方法一实现如下：

/*
struct TreeNode {
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
    TreeNode(int x) :
            val(x), left(NULL), right(NULL) {
    }
};*/
int TreeDepth(TreeNode*root)
{
    if(!root)
        return 0;
    vector<int> path;
    int maxlength=0;
    return findpath(root,path,maxlength);
}
int findpath(TreeNode*root,vector<int>&path,int &maxlength)
{
    path.push_back(root->val);
    if(!root->left&&!root->right)
    {
        if(maxlength<path.size())
            maxlength=path.size();
    }
    if(root->left)
        findpath(root->left,path,maxlength);
    if(root->right)
        findpath(root->right,path,maxlength);
    path.pop_back();
    return maxlength;
}

方法二，实现如下：

/*
struct TreeNode {
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
    TreeNode(int x) :
            val(x), left(NULL), right(NULL) {
    }
};*/
int TreeDepth(TreeNode*root)
{
    if(!root)
        return 0;
    int left_depth=TreeDepth(root->left);
    int right_depth=TreeDepth(root->right);
    return left_depth>right_depth? (left_depth+1):(right_depth+1);
}

题目二：输入一颗二叉树的根节点，判断该二叉树是不是平衡二叉树。二叉树的任意节点的左右子树的高度之差不超过一即为平衡二叉树。
分析：方法一：借助上面求树深度的方法，我们可以求每一个节点左、右子树的深度并且判断两者相差是否超过一，来判断是否为平衡二叉树。
实现如下：

/*
struct TreeNode {
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
    TreeNode(int x) :
            val(x), left(NULL), right(NULL) {
    }
};*/
bool isBanlanced(TreeNode*root)
{
    if(!root)
        return true;
    int left_depth=TreeDepth(root->left);
    int right_depth=TreeDepth(root->right);
    int diff=left_depth-right_depth;
    if(diff>1||diff<-1)
        return false;
    return isBanlanced(root->left)&&isBanlanced(root->right);
}

方法二：上述方法虽然简单，但是一个节点会被重复遍历，当我们判断一个节点是否是平衡的时候要判断它的左右子树，这样做的效率不高。我们可以采用后序遍历的方式，在遍历到一个节点的时候我们呢已经遍历了他的左右子树。在我们求树的深度时，记录出每个节点的高度，就可以一边遍历一边判断每个节点是不是平衡的。
实现如下：

/*
struct TreeNode {
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
    TreeNode(int x) :
            val(x), left(NULL), right(NULL) {
    }
};*/
bool isBanlanced(TreeNode*root,int &pdepth)
{
    if(root==NULL)
    {
        pdepth=0;
        return true;    
    }
    int left_length=0;
    int right_length=0;
    if(isBanlanced(root->left,left_length)&&isBanlanced(root->right,right_length))
    {
        int diff=left-right;
        if(diff>=-1&&diff<=1)
        {
            pdepth=1+(left_length>right_length?left_length:right_length);
            return true;
        }
    }
    return false;
}
bool isBanlanced(TreeNode*root)
{
    int pdepth=0;
    return isBanlanced(root,pdepth);
}