代码训练营Day.17 | 110. 平衡二叉树

110. 平衡二叉树

1. LeetCode链接

110. 平衡二叉树 - 力扣（LeetCode）

2. 题目描述

3. 解法

? ? ? ? 首先明确，什么是平衡二叉树。其次明确，二叉树的高度和深度表示什么。

? ? ? ? 深度：从上（根节点）往下数。高度：从下（叶子节点）往上数。由平衡二叉树的特性得知，它所需的特性是高度！

? ? ? ? 由下往上的递归方法，是首选。该树是否是平衡二叉树取决于两点：1. 左右子树都是平衡二叉树；2. 左右子树高度差<=1。

? ? ? ? 1. 参数和输出。参数：树节点。输出：双输出，bool、int。

? ? ? ? 2. 终止条件。当前树节点为NULL。则返回true和0；

? ? ? ? 3. 单层递归逻辑。判断左子树是否为平衡二叉树、判断右子树是否为平衡二叉树、判断左右子树高度差是否相差小于等于1。

class Solution {
public:
    int result;
    tuple<bool, int> isB(TreeNode* root) {
        if (root == NULL) return make_pair(true, 0);
        bool a = false;
        tuple<bool, int> l = isB(root->left);
        tuple<bool, int> r = isB(root->right);
        bool lb = get<0>(l);
        bool rb = get<0>(r);
        int left = get<1>(l);
        int right = get<1>(r);
        if (left == right || abs(left - right) == 1) a = true; 
        return make_pair(a && lb && rb, 1 + max(left, right));
    }
    bool isBalanced(TreeNode* root) {
        return get<0>(isB(root));
    }
};

? ? ? ? 关于自下而上求高度的递归，还有比较巧妙的解法，即该节点是平衡二叉树，则返回正确高度，如果不是，则返回-1。因为一棵树的高度不可能是-1，所以可以这么搞。

class Solution {
public:
    int isB(TreeNode* root) {
        if (root == NULL) return 0;
        int left = isB(root->left);
        int right = isB(root->right);
        if (left == -1 || right == -1) return -1;
        return abs(left - right) > 1 ? -1 : 1 + max(left, right);
    }
    bool isBalanced(TreeNode* root) {
        return isB(root) == -1 ? false : true;
    }
};

257. 二叉树的所有路径

1. LeetCode链接

257. 二叉树的所有路径 - 力扣（LeetCode）

2. 题目描述

3. 想法

1. 前序遍历递归

? ? ? ? 设置一个类内全局变量vector<string>。

? ? ? ? 额外构造函数执行前序遍历的递归方法。

? ? ? ? 1. 参数和输出。参数：树节点和路径。

? ? ? ? 2. 终止条件。无。

? ? ? ? 3. 单层递归逻辑。path中加入当前节点。如果是叶子节点，push到result中；否则，只递归入非NULL子节点，且在进入前path加入“->”。

代码随想录中，提到回溯，其实就是进入left后再进right时，path值并没有被left影响。

class Solution {
public:
    vector<string> result;
    void order(TreeNode* root, string path) {
        path += to_string(root->val);
        if (root->left == NULL && root->right == NULL) result.push_back(path);
        if (root->left != NULL) {
            string lp = path + "->";
            order(root->left, lp);
        }
        if (root->right != NULL) {
            string rp = path + "->";
            order(root->right, rp);
        }
    }
    vector<string> binaryTreePaths(TreeNode* root) {
        order(root, "");
        return result;
    }
};

404. 左叶子之和

1. LeetCode链接

404. 左叶子之和 - 力扣（LeetCode）

2. 题目描述

3. 解法

仍然是前序遍历递归法。

只有当判断出当前节点的左子节点是叶子节点时，才加到result中。

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

普通递归遍历，只加左叶子节点，其他都当0加。?

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);
    }
};

中序遍历迭代法（不熟练）

class Solution {
public:
    int sumOfLeftLeaves(TreeNode* root) {
        stack<TreeNode*> st;
        // st.push(root);
        int result = 0;
        TreeNode* cur = root;
        while (!st.empty() || cur != NULL) {
            if (cur != NULL) {
                if (cur->left != NULL && cur->left->left == NULL && cur->left->right == NULL) {
                    result += cur->left->val;
                    cur = cur->right;
                    continue;
                }
                st.push(cur);
                cur = cur->left;
            } else {
                cur = st.top();
                st.pop();
                cur = cur->right;
            }
        }
        return result;
    }
};

统一迭代

class Solution {
public:
    int sumOfLeftLeaves(TreeNode* root) {
        stack<TreeNode*> st;
        st.push(root);
        int result = 0;
        while (!st.empty()) {
            TreeNode* cur = st.top();
            if (cur != NULL) {
                st.pop();
                if (cur->right != NULL) st.push(cur->right);
                if (cur->left != NULL && cur->left->left == NULL && cur->left->right == NULL) {
                    result += cur->left->val;
                    cur = cur->right;
                    continue;
                }
                if (cur->left != NULL) st.push(cur->left);
                st.push(cur);
                st.push(NULL);
            } else {
                st.pop();
                st.pop();
            }
        }
        return result;
    }
};