算法学习【二叉树篇】(4)

平衡二叉树

求深度适合用前序遍历，而求高度适合用后序遍历

class Solution {
public:
    // 返回以该节点为根节点的二叉树的高度，如果不是二叉搜索树了则返回-1
    int getHeight(TreeNode* node) {
        if (node == NULL) {
            return 0;
        }
        int leftHeight = getHeight(node->left);
        if (leftHeight == -1) return -1;
        int rightHeight = getHeight(node->right);
        if (rightHeight == -1) return -1;
        return abs(leftHeight - rightHeight) > 1 ? -1 : 1 + max(leftHeight, rightHeight);
    }
    bool isBalanced(TreeNode* root) {
        return getHeight(root) == -1 ? false : true;
    }
};

左叶子之和

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    void traversal(TreeNode* node,int* sum){
        
        if(node->left==NULL&&node->right==NULL){
            return;
        }
        if(node->left&&!node->left->left&&!node->left->right){
            *sum+=node->left->val;
            traversal(node->left,sum);
        }
        else if(node->left){
            traversal(node->left,sum);
        }
        if(node->right){
            traversal(node->right,sum);
        }
    }
    int sumOfLeftLeaves(TreeNode* root) {
        int sum=0;
        int* p;
        p=∑
        if(root==NULL) return 0;
        traversal(root,p);
        return *p;
    }
};

找树左下角的值

迭代法

class Solution {
public:
    int findBottomLeftValue(TreeNode* root) {
        if(root==NULL) return 0;
        queue<TreeNode*> que;
        que.push(root);
        int result=0;
        while(!que.empty())&#123;
            int size = que.size();
            vector<int> value;
            for(int i=0;i<size;i++)&#123;
                TreeNode* node = que.front();
                que.pop();
                value.push_back(node->val);
                if(node->left) que.push(node->left);
                if(node->right) que.push(node->right);
            &#125;
            result=value[0];
        &#125;
        return result;
    &#125;
&#125;;