平衡二叉树判断、完全二叉树判断

逃离我推掉我的手 2022-06-09 09:36 223阅读 0赞

*   *   *  平衡二叉树判断
         *  完全二叉树判断

--------------------

### 平衡二叉树判断 ###

有一棵二叉树，请设计一个算法判断这棵二叉树是否为平衡二叉树。

给定二叉树的根结点root，请返回一个bool值，代表这棵树是否为平衡二叉树。

**我的提交**

# -*- coding:utf-8 -*-
    
    # class TreeNode:
    # def __init__(self, x):
    # self.val = x
    # self.left = None
    # self.right = None
    class CheckBalance:
        def getDepth(self, root):
            if not root:
                return 0
            ldepth = self.getDepth(root.left)
            rdepth = self.getDepth(root.right)
            return max(ldepth, rdepth) + 1
    
        def check(self, root):
            # write code here
            if not root:
                return True
            ldepth = self.getDepth(root.left)
            rdepth = self.getDepth(root.right)
            diff = abs(ldepth - rdepth)
            if diff > 1:
                return False
            return self.check(root.left) and self.check(root.right)

**参考答案**

/* struct TreeNode { int val; struct TreeNode *left; struct TreeNode *right; TreeNode(int x) : val(x), left(NULL), right(NULL) { } };*/
    
    class CheckBalance {
    public:
        int chk(TreeNode* rt){
            if(rt == NULL) return 0;
            int l = chk(rt->left),r = chk(rt->right);
            if(l < 0 || r < 0) return -1;
            if(abs(r - l) > 1) return -1;
            return r > l ? r + 1 : l + 1;
        }
        bool check(TreeNode* root) {
            return chk(root) >= 0;
        }
    };

### 完全二叉树判断 ###

有一棵二叉树,请设计一个算法判断它是否是完全二叉树。

给定二叉树的根结点root，请返回一个bool值代表它是否为完全二叉树。树的结点个数小于等于500

**我的提交**

# -*- coding:utf-8 -*-
    
    # class TreeNode:
    # def __init__(self, x):
    # self.val = x
    # self.left = None
    # self.right = None
    class CheckCompletion:
        def chk(self, root):
            # write code here
            if not root:
                return True
            queue = []
            stop = False
            queue.append(root)
            while queue:
                p = queue.pop(0)
                if p.left:
                    if stop:
                        return False
                    queue.append(p.left)
                else:
                    stop = True
                if p.right:
                    if stop:
                        return False
                    queue.append(p.right)
                else:
                    stop = True
            return True

**参考答案**

/* struct TreeNode { int val; struct TreeNode *left; struct TreeNode *right; TreeNode(int x) : val(x), left(NULL), right(NULL) { } };*/
    
    class CheckCompletion {
    public:
        bool chk(TreeNode* root) {
            TreeNode *q[800],*now;
            int head = 0,tail = 0;
            q[tail ++] = root;
            while(head != tail){
                now = q[head ++];   
                if(now->left) q[tail ++] = now->left;
                if(now->right) q[tail ++] = now->right;
            }
            bool flag = false;
            for(int i = 0;i < tail;++ i)
            if(q[i]->left == NULL || q[i]->right == NULL){
                if(q[i]->right && q[i]->left == NULL) return false;
                if(!flag) flag = true;
                else if(q[i]->left || q[i]->right) return false;
            }
            return true;
        }
    };