二叉树应用_二叉树深度

妖狐艹你老母 2022-05-22 03:41 319阅读 0赞

题目：输入一颗二叉树的根节点，求该树的深度。  
分析：方法一：在[二叉树中和为某一值的路径][Link 1]中已经知道了如何存取树的一条路径，这里我们可以用此方法求出树的最长路径，也就是树的深度。方法二：树的深度即是左、右子树中深度较大的值加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);
    }

[Link 1]: https://blog.csdn.net/xc13212777631/article/details/80681231