代码随想录算法训练营第17天 | 110.平衡二叉树、257. 二叉树的所有路径、404.左叶子之和

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

思路:遍历每个节点，如果该节点左右子树相差大于1则返回false，如果全部符合条件则返回true

我的AC代码

//时间复杂度O(n2),空间复杂度O(n2)
class Solution {
public:
    int get_depth(TreeNode* node) {
        if(node == nullptr) {
            return 0;
        }
        int left = get_depth(node->left);
        int right = get_depth(node->right);
        return 1 + max(left, right);
    }
    bool judge(TreeNode* node) {
        if(node == nullptr) {
            return true;
        }
        return judge(node->left) && judge(node->right) && abs(get_depth(node->left) - get_depth(node->right)) <= 1;
    }
    bool isBalanced(TreeNode* root) {
        if(root == nullptr) {
            return true;
        }
        return judge(root);
    }
};

标准答案

递归法(后序遍历)

//时间复杂度O(n),空间复杂度O(n)
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;
    }
};

迭代法(模拟后序遍历)

//时间复杂度O(n2),空间复杂度O(n2)
class Solution {
private:
    int getDepth(TreeNode* cur) {
        stack<TreeNode*> st;
        if (cur != NULL) st.push(cur);
        int depth = 0; // 记录深度
        int result = 0;
        while (!st.empty()) {
            TreeNode* node = st.top();
            if (node != NULL) {
                st.pop();
                st.push(node);                          // 中
                st.push(NULL);
                depth++;
                if (node->right) st.push(node->right);  // 右
                if (node->left) st.push(node->left);    // 左

            } else {
                st.pop();
                node = st.top();
                st.pop();
                depth--;
            }
            result = result > depth ? result : depth;
        }
        return result;
    }

public:
    bool isBalanced(TreeNode* root) {
        stack<TreeNode*> st;
        if (root == NULL) return true;
        st.push(root);
        while (!st.empty()) {
            TreeNode* node = st.top();                       // 中
            st.pop();
            if (abs(getDepth(node->left) - getDepth(node->right)) > 1) {
                return false;
            }
            if (node->right) st.push(node->right);           // 右（空节点不入栈）
            if (node->left) st.push(node->left);             // 左（空节点不入栈）
        }
        return true;
    }
};

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

思路:用递归前序遍历二叉树，每遇到一个节点就将节点值加入路径中，然后判断该节点左右两侧是否还有孩子，如果有则用此时的路径值创建一个新的字符串带入递归函数，否则宣告该路径走到尽头，将答案填入数组ans中，此思路中回溯的方法就是创建一个新的字符串

技巧：做好回溯的关键是：注意到回溯和递归是一一对应的，有一个递归，就要有一个回溯

理论上下面的几种方法使用的空间复杂度都是接近的，但是貌似因为递归法要调用系统堆栈所以空间占用略大于迭代法

我的AC代码

递归法(直接创建新字符串不回溯)

// 时间复杂度O(n),空间复杂度O(n)
class Solution {
public:
    void findall(TreeNode* node, vector<string>& ans,  string& s) {
        if(node->left == nullptr && node->right == nullptr) {
            string b = s + to_string(node->val);
            ans.push_back(b);
        }
        string a = s + to_string(node->val);
        a += "->";
        if(node->left) {
            findall(node->left, ans, a);
        }
        if(node->right) {
            findall(node->right, ans, a);
        }
    }
    vector<string> binaryTreePaths(TreeNode* root) {
        vector<string> ans;
        string s = "";
        findall(root, ans, s);
        return ans;
    }
};

复刻标准答案迭代法(前序遍历)

// 时间复杂度O(n),空间复杂度O(n)
class Solution {
public:
    vector<string> binaryTreePaths(TreeNode* root) {
        stack<TreeNode*> st;
        stack<string> path;
        vector<string> ans;
        if(root == nullptr) {
            return ans;
        }
        st.push(root);
        string a = to_string(root->val);
        path.push(a);
        while(!st.empty()) {
            TreeNode* tmp = st.top();
            st.pop();
            string stmp = path.top();
            path.pop();
            if(!tmp->left && !tmp->right) {
                ans.push_back(stmp);
            }
            if(tmp->left) {
                st.push(tmp->left);
                path.push(stmp + "->" + to_string(tmp->left->val));
            }
            if(tmp->right) {
                st.push(tmp->right);
                path.push(stmp + "->" + to_string(tmp->right->val));
            }
        }
        return ans;
    }
};

标准答案

递归版本一

//时间复杂度O(n),空间复杂度O(n)
// 版本一
class Solution {
private:

    void traversal(TreeNode* cur, vector<int>& path, vector<string>& result) {
        path.push_back(cur->val); // 中，中为什么写在这里，因为最后一个节点也要加入到path中 
        // 这才到了叶子节点
        if (cur->left == NULL && cur->right == NULL) {
            string sPath;
            for (int i = 0; i < path.size() - 1; i++) {
                sPath += to_string(path[i]);
                sPath += "->";
            }
            sPath += to_string(path[path.size() - 1]);
            result.push_back(sPath);
            return;
        }
        if (cur->left) { // 左 
            traversal(cur->left, path, result);
            path.pop_back(); // 回溯
        }
        if (cur->right) { // 右
            traversal(cur->right, path, result);
            path.pop_back(); // 回溯
        }
    }

public:
    vector<string> binaryTreePaths(TreeNode* root) {
        vector<string> result;
        vector<int> path;
        if (root == NULL) return result;
        traversal(root, path, result);
        return result;
    }
};

递归版本二

//时间复杂度O(n),空间复杂度O(n)
// 版本二
class Solution {
private:

    void traversal(TreeNode* cur, string path, vector<string>& result) {
        path += to_string(cur->val); // 中
        if (cur->left == NULL && cur->right == NULL) {
            result.push_back(path);
            return;
        }
        if (cur->left) traversal(cur->left, path + "->", result); // 左
        if (cur->right) traversal(cur->right, path + "->", result); // 右
    }

public:
    vector<string> binaryTreePaths(TreeNode* root) {
        vector<string> result;
        string path;
        if (root == NULL) return result;
        traversal(root, path, result);
        return result;

    }
};

递归版本三

//时间复杂度O(n),空间复杂度O(n)
// 版本三
class Solution {
private:
    void traversal(TreeNode* cur, string path, vector<string>& result) {
        path += to_string(cur->val); // 中，中为什么写在这里，因为最后一个节点也要加入到path中
        if (cur->left == NULL && cur->right == NULL) {
            result.push_back(path);
            return;
        }
        if (cur->left) {
            path += "->";
            traversal(cur->left, path, result); // 左
            path.pop_back(); // 回溯 '>'
            path.pop_back(); // 回溯 '-'
        }
        if (cur->right) {
            path += "->";
            traversal(cur->right, path, result); // 右
            path.pop_back(); // 回溯'>'
            path.pop_back(); // 回溯 '-'
        }
    }

public:
    vector<string> binaryTreePaths(TreeNode* root) {
        vector<string> result;
        string path;
        if (root == NULL) return result;
        traversal(root, path, result);
        return result;

    }
};

迭代(前序遍历)

//时间复杂度O(n),空间复杂度O(n)
class Solution {
public:
    vector<string> binaryTreePaths(TreeNode* root) {
        stack<TreeNode*> treeSt;// 保存树的遍历节点
        stack<string> pathSt;   // 保存遍历路径的节点
        vector<string> result;  // 保存最终路径集合
        if (root == NULL) return result;
        treeSt.push(root);
        pathSt.push(to_string(root->val));
        while (!treeSt.empty()) {
            TreeNode* node = treeSt.top(); treeSt.pop(); // 取出节点 中
            string path = pathSt.top();pathSt.pop();    // 取出该节点对应的路径
            if (node->left == NULL && node->right == NULL) { // 遇到叶子节点
                result.push_back(path);
            }
            if (node->right) { // 右
                treeSt.push(node->right);
                pathSt.push(path + "->" + to_string(node->right->val));
            }
            if (node->left) { // 左
                treeSt.push(node->left);
                pathSt.push(path + "->" + to_string(node->left->val));
            }
        }
        return result;
    }
};

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

思路:使用迭代法前序遍历二叉树，如果当前节点的右节点非空，直接推入栈，如果当前节点的左节点非空，就在后面再推入一个标记节点(该节点值为特殊值或者改节点为空节点都可以)，如果当前遍历到的节点是标记节点，那么先弹出，然后判断此时在栈顶的节点是否无左右孩子，如果无左右孩子则说明是题目描述的左叶子，否则只弹出标记节点

我的AC代码

//时间复杂度O(n),空间复杂度O(n)
class Solution {
public:
    int sumOfLeftLeaves(TreeNode* root) {
        int sum = 0;
        stack<TreeNode*> st;
        if(root == nullptr) {
            return 0;
        }
        st.push(root);
        while(!st.empty()) {
            TreeNode* tmp = st.top();
            st.pop();
            if(tmp->right) {
                st.push(tmp->right);
            }
            if(tmp->left) {
                st.push(tmp->left);
                TreeNode* sign = new TreeNode(-9999);
                st.push(sign);
            }
            if(tmp->val == -9999) {
                if(!st.top()->left && !st.top()->right) {
                    sum += st.top()->val;
                    st.pop();
                }
            }
        }
        return sum;
    }
};

标准答案

递归1

//时间复杂度O(n),空间复杂度O(n)
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 && !root->left->left && !root->left->right) { // 左子树就是一个左叶子的情况
            leftValue = root->left->val;
        }
        int rightValue = sumOfLeftLeaves(root->right);  // 右

        int sum = leftValue + rightValue;               // 中
        return sum;
    }
};

递归2

//时间复杂度O(n),空间复杂度O(n)
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);
    }
};

迭代法

//时间复杂度O(n),空间复杂度O(n)
class Solution {
public:
    int sumOfLeftLeaves(TreeNode* root) {
        stack<TreeNode*> st;
        if (root == NULL) return 0;
        st.push(root);
        int result = 0;
        while (!st.empty()) {
            TreeNode* node = st.top();
            st.pop();
            if (node->left != NULL && node->left->left == NULL && node->left->right == NULL) {
                result += node->left->val;
            }
            if (node->right) st.push(node->right);
            if (node->left) st.push(node->left);
        }
        return result;
    }
};

额外题目

100. 相同的树 - 力扣（LeetCode）

我的AC代码

//时间复杂度O(n),空间复杂度O(n)
class Solution {
public:
    bool same(TreeNode* l, TreeNode* r) {
        if(l == nullptr && r == nullptr) {
            return true;
        }
        if(l == nullptr && r !=nullptr) {
            return false;
        }
        if(l != nullptr && r ==nullptr) {
            return false;
        }
        if(l->val != r->val) {
            return false;
        }
        return same(l->left, r->left) && same(l->right, r->right);
    }
    bool isSameTree(TreeNode* p, TreeNode* q) {
        return same(p, q);
    }
};

572. 另一棵树的子树 - 力扣（LeetCode）

我的AC代码

//时间复杂度O(n2),空间复杂度O(n)
class Solution {
public:
    bool same(TreeNode* l, TreeNode* r) {
        if(!l && !r) {
            return true;
        }
        if(l && !r) {
            return false;
        }
        if(!l && r) {
            return false;
        }
        if(r->val != l->val) {
            return false;
        }
        return same(l->left, r->left) && same(l->right, r->right);
    }
    bool isSubtree(TreeNode* root, TreeNode* subRoot) {
        stack<TreeNode*> st;
        st.push(root);
        while(!st.empty()) {
            TreeNode* tmp = st.top();
            if(same(tmp, subRoot)) {
                return true;
            }
            st.pop();
            if(tmp->left) {
                st.push(tmp->left);
            }
            if(tmp->right) {
                st.push(tmp->right);
            }
        }
        return false;
    }
};