algorithm/source/judgeFullTree.cpp at main · butcher-x/algorithm · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
//
// Created by ButcherX on 23-10-28.
//
#include"../header/treenode.h"
//个人解法
//0-null, 1-true, 2-false
int judgeFullTree_in(TreeNode* root)
{
   if(root == nullptr)
       return 0;
   int lc = judgeFullTree_in(root->left);
   int rc = judgeFullTree_in(root->right);
   if(lc == 0 && rc == 0)
       return 1;
   if(lc == 1 && rc == 1)
       return 1;
   if(lc + rc == 1)
       return 2;
   if(lc == 2 || rc == 2)
       return 2;
}

bool judgeFullTree(TreeNode* root)
{
    int ret = judgeFullTree_in(root);
    if(ret == 0 || ret == 1)
        return true;
    else
        return false;
}
//=======================================
//官方解法：
bool isFullBinaryTree(TreeNode* root) {
    // 如果树为空，则是满二叉树
    if (root == nullptr) {
        return true;
    }

    // 如果节点没有左子树和右子树，它是叶子节点
    if (root->left == nullptr && root->right == nullptr) {
        return true;
    }

    // 如果节点有左子树和右子树，继续检查它们
    if (root->left && root->right) {
        return isFullBinaryTree(root->left) && isFullBinaryTree(root->right);
    }

    // 如果节点只有左子树或右子树，不是满二叉树
    return false;
}