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

110.平衡二叉树

代码随想录链接

题目

判断一个二叉树是否是平衡二叉树, 即该二叉树的任意一个子树的左右子树高度差都不超过1.

自己的想法

递归判断左右子树的高度是否满足要求.

题解

递归法：

class Solution {
private:
    int getHeight(TreeNode* node) {
        if (!node) return 0;
        int leftHeight = getHeight(node -> left);   // 递归判断左子树的高度
        if (leftHeight == -1) return -1;    // 若左子树不平衡，则直接返回-1
        int rightHeight = getHeight(node -> right); // 递归判断右子树的高度
        if (rightHeight == -1) return -1;   // 若右子树不平衡，则直接返回-1
        return abs(leftHeight - rightHeight) > 1 ? -1 : 1 + max(leftHeight, rightHeight);   // 若左右子树平衡，根据左右子树高度差判断
    }
public:
    bool isBalanced(TreeNode* root) {
        return getHeight(root) == -1 ? false : true;
    }
};

迭代法：

class Solution {
private:
    int getDepth(TreeNode* cur) {   // 层序遍历，获得输入节点的高度
        if (!cur) return 0;
        int depth = 0;
        queue<TreeNode *> que;
        que.push(cur);
        while (!que.empty()) {
            int qsize = que.size();
            depth++;
            for (int i = 0; i < qsize; i++) {
                TreeNode *node = que.front();
                que.pop();
                if (node -> left) que.push(node -> left);
                if (node -> right) que.push(node -> right);
            }
        }
        return depth;
    }
public:
    bool isBalanced(TreeNode* root) {
        if (!root) return true;
        stack<TreeNode *> st;
        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.二叉树的所有路径

代码随想录链接

题目

返回从根节点出发到达每个叶子节点的路径。

自己的想法

前序遍历，访问一个节点的操作是判断其是否为叶子节点，若为叶子节点，则从根节点到这个节点的路径记录下来。

题解

递归法：

class Solution {
private:
    void traversal(TreeNode *cur, vector<int> &path, vector<string> &result) {
        path.push_back(cur -> val); // 访问到这个节点时，再将该节点加入路径
        if (!(cur -> left) && !(cur -> right)) {    // 如果是叶子节点，就记录路径
            string sPath;
            for (int i = 0; i < path.size() - 1; i++) {
                sPath += to_string(path[i]);
                sPath += "->";
            }
            sPath += to_string(cur -> val);
            result.push_back(sPath);
        }
        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) return result;
        traversal(root, path, result);
        return result;
    }
};

迭代法：

前序遍历，并使用栈来记录当前遍历从根节点出发的路径。

class Solution {
public:
    vector<string> binaryTreePaths(TreeNode* root) {
        vector<string> result;
        stack<string> pathSt;
        stack<TreeNode*> st;
        if (!root) return result;
        st.push(root);
        pathSt.push(to_string(root -> val));
        while (!st.empty()) {   // 使用栈来遍历节点
            TreeNode *node = st.top(); st.pop();
            string path = pathSt.top(); pathSt.pop();
            if (!(node -> left) && !(node -> right)) {
                result.push_back(path);
            }   // 如果当前节点是椰子节点, 就记录下来该节点的路径
            if (node -> right) {
                st.push(node -> right);
                pathSt.push(path + "->" + to_string(node -> right -> val));
            }   // 栈内推入节点和节点的路径
            if (node -> left) {
                st.push(node -> left);
                pathSt.push(path + "->" + to_string(node -> left -> val));
            }

        }
        return result;
    }
};

404.左叶子之和

代码随想录链接

题目

返回给定的二叉树的所有左叶子结点的值之和.

自己的想法

在遍历的时候加一个判断, 如果左孩子存在且是叶子结点, 就将左孩子的值加和.

题解

递归法:

class Solution {
public:
    int sumOfLeftLeaves(TreeNode* root) {
        if (!root) return 0;
        if (!(root -> left) && !(root -> right)) return 0;
        int leftVal = sumOfLeftLeaves(root -> left);    // 求左子树中的左叶子结点值之和
        if (root -> left && !(root -> left -> left) && !(root -> left -> right)) {  // 如果左孩子是个叶子结点, 将其值加和
            leftVal += root -> left -> val;
        }
        int rightVal = sumOfLeftLeaves(root -> right);  // 求右子树中左叶子结点值之和

        return leftVal + rightVal;
    }
};

迭代法:

class Solution {
public:
    int sumOfLeftLeaves(TreeNode* root) {
        int result = 0;
        if (!root) return result;
        stack<TreeNode *> st;
        st.push(root);
        while (!st.empty()) {   // 统一写法的中序遍历
            TreeNode *node = st.top();
            if (node) {
                st.pop();
                st.push(node);
                st.push(NULL);

                if (node -> right) st.push(node -> right);
                if (node -> left) st.push(node -> left);
            } else {    // "访问"一个节点, 判断左孩子是不是叶子结点
                st.pop();
                node = st.top();
                st.pop();
                if (node -> left && !(node -> left -> left) && !(node -> left -> right)) result += node -> left -> val;
            }
        }
        return result;
    }
};