lc110 平衡二叉树

递归法

本题目与求二叉树高度有些类型，使用后序遍历，若节点子树为平衡二叉树则返回当前节点高度，若节点子树为不平衡二叉树则返回-1

class Solution {
public:
    int getHeight(TreeNode* node){  //不平衡返回-1，平衡返回高度
        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;
        if(abs(leftHeight-rightHeight) > 1) return -1;
        else return(1 + max(leftHeight,rightHeight));
    }
    bool isBalanced(TreeNode* root) {
        return(getHeight(root) != -1);
    }
};

本题使用迭代法的效率并不高，暂时跳过

lc257 二叉树的所有路径

本题可继续深入

第一次接触到了回溯，这道题目使用的是前序遍历，为了从根节点开始按顺序输出路径

class Solution {
public:
    void traversal(TreeNode* node, vector<int>& path, vector<string>& result){
        path.push_back(node->val);   //中
        if(node->left == NULL && node->right == NULL){
            string path_constructor;
            for(int i=0;i<path.size() - 1;i++){
                path_constructor += to_string(path[i]);
                path_constructor += "->";
            }
            path_constructor += to_string(path[path.size() - 1]);
            result.push_back(path_constructor);
            return;
        }
        if(node->left){
            traversal(node->left,path,result);
            path.pop_back();
        }
        if(node->right){
            traversal(node->right,path,result);
            path.pop_back();
        }
    }
    vector<string> binaryTreePaths(TreeNode* root) {
        vector<string> result;
        vector<int> path;
        if(root==NULL) return result;
        traversal(root,path,result);
        return result;
    }
};

lc404 左叶子之和

以下解法可以明显看出来后序遍历过程，题目重点是搞清楚左叶子的判断条件（需要父节点判断）

class Solution {
public:
    int sumOfLeftLeaves(TreeNode* root) {
        if(root == NULL) return 0;
        if(root->left == NULL && root->right == NULL) return 0;
        int leftValue = sumOfLeftLeaves(root->left);
        if(root->left!=NULL && root->left->left == NULL && root->left->right == NULL){
            leftValue = root->left->val;
        }
        int rightValue = sumOfLeftLeaves(root->right);
        int sum = leftValue + rightValue;
        return sum;
    }
};

可以简化

class Solution {
public:
    int sumOfLeftLeaves(TreeNode* root) {
        if (root == NULL) return 0;
        int leftValue = 0;
        if (root->left != NULL && root->left->left == NULL && root->left->right == NULL) {
            leftValue = root->left->val;
        }
        return leftValue + sumOfLeftLeaves(root->left) + sumOfLeftLeaves(root->right);
    }
};