algorithm - 左子树的深度小于右子树的深度

Question

我需要一种算法来检查二叉树中的每个节点，如果左子树的深度小于右子树的深度，则返回 true 或 false。 它必须在 O(n) 内。

我想建立一个函数来计算每个子树的深度，并用它来检查每个节点左子树的深度是否小于右子树的深度，但我认为这将是 O(n^2) .

Answer 1

递归dfs解决方案:

struct node{
    int val;
    bool leftGreater;
    struct node *left, *right;
};

int solve(Node *n){
    if(n == NULL){
        return 0;
    }
    int left = solve(n->left) + 1;
    int right = solve(n->right) + 1;
    if(left > right){
        n->leftGreater = true;
    }else{
        n->leftGreater = false;
    }
return max(left, right);
}