首页 / 算法 / Balanced Binary Tree （二叉树DFS）

Balanced Binary Tree （二叉树DFS）

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了Balanced Binary Tree （二叉树DFS），小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含1147字，纯文字阅读大概需要2分钟。

内容图文

Given a binary tree, determine if it is height-balanced.

For this problem, a height-balanced binary tree is defined as a binary tree in which the depth of the two subtrees of every node never differ by more than 1.

判断一棵树是否为平衡二叉树。

思路：典型的递归，从第一个根节点开始，看左子树和右子树的深度差值是否小于等于1，然后再看由根节点的左孩子和右孩子构成的两课树是否都符合条件。

代码：

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

            private
            :
    
            int
             maxdepth;

            public
            :
    
            void solve(TreeNode *root,int depth){
        if(root==NULL)
            return;
        if(depth>maxdepth)
            maxdepth=depth;
        solve(root->left,depth+1);
        solve(root->right,depth+1);
    }
    int getDepth(TreeNode *root) {
        maxdepth=0;
        solve(root,1);
        return maxdepth;
    }
    bool isBalanced(TreeNode *root) {
        if(root==NULL) 
            returntrue;
        int l,r;
        if(root->left!=NULL){
            l=getDepth(root->left);
        }else{
            l=0;
        }
        if(root->right!=NULL){
            r=getDepth(root->right);
        }else{
            r=0;
        }
        return abs(l-r)<=1&&isBalanced(root->left)&&isBalanced(root->right);
    }
};

 

原文：http://www.cnblogs.com/fightformylife/p/4079496.html

内容总结

以上是互联网集市为您收集整理的Balanced Binary Tree （二叉树DFS）全部内容，希望文章能够帮你解决Balanced Binary Tree （二叉树DFS）所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端

扫描二维码推送至手机访问。

本文链接：https://qyyshop.com/info/1131312.html

来源：【匿名】