526互联

算法学习Day17二叉树迭迭迭迭代

发布时间 2023-12-30 10:50:30作者: HQWQF

Day17迭迭迭迭代

By HQWQF 2023/12/28

笔记

110.平衡二叉树

给定一个二叉树，判断它是否是高度平衡的二叉树。

本题中，一棵高度平衡二叉树定义为：

一个二叉树_每个节点_ 的左右两个子树的高度差的绝对值不超过 1 。

示例 1：

输入： root = [3,9,20,null,null,15,7]
输出： true

递归法

我们这里再复习下概念：
二叉树节点的深度：指从该节点到根节点的最长简单路径边的条数。
二叉树节点的高度：指从该节点到叶子节点的最长简单路径边的条数。

关于根节点的深度究竟是1 还是 0，不同的地方有不一样的标准，力扣上是1。

为了判断每个节点的左右两个子树的高度差，我们需要获得子树的高度，在得出两个子树的高度差后我们可以判断是否绝对值超过 1，超过则通过引用参数给变量赋false。

递归法代码

class Solution {
public:
    bool isBalanced(TreeNode* root) {
        bool res = true;
        getdepth(root,res);
        return res;
    }
    int getdepth(TreeNode* node,bool &res)
    {
        if(node == nullptr){return 0;}
        int l = getdepth(node->left,res) + 1;
        int r = getdepth(node->right,res) + 1;
        if(abs(l-r) > 1){res = false;}
        return max(l,r);
    }
};

其实我们可以在碰到节点左右不平衡时用特殊的返回值进行标识，比如-1，只要有子树返回了-1，就继续返回-1，这样我们就可以省下一个参数了。

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

迭代法

求高度需要一个回溯的过程，如果从叶子节点向上处理会容易一些，所以我们配合栈以实现类似回溯的效果来求一个节点的高度。

然后我们可以使用栈来对节点进行遍历，对每个节点的左右孩子求高度，不平衡就返回false.

迭代法代码

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

注释

  • 递归时，如果是利用递归去深入，代码里写fun(node,deep+1)，如果是利用递归去回溯，代码里写fun(node) + 1
  • 其实这里的迭代法的效率比递归慢不少，但是递归本身就是用栈实现的啊，那是不是说有比这个迭代法更快的迭代法呢？

257.二叉树的所有路径

class Solution {
public:
    vector<string> binaryTreePaths(TreeNode* root) {
        vector<string> resList;
        string res ="";
        test(root,res,resList);
        return resList;
    }
    void traversal(TreeNode* node,string res,vector<string> &resList)
    {
        if(node->left == nullptr && node->right == nullptr)
        {
            resList.push_back(res + to_string(node->val));
            return;
        }
        if(node->left)
            traversal(node->left,res + to_string(node->val)+ "->",resList);
        if(node->right)
            traversal(node->right,res +  to_string(node->val)+ "->",resList);
    }
};

迭代法

迭代法我们可以在栈遍历节点的基础上，使用一个和节点栈结构类似的路径栈来存储根节点到当前节点的路径，在遍历到下一个节点时会通过当前节点在路径栈中的值设置下一个节点在路径栈中对应的值，一样是碰到叶子就把路径加入链表。

迭代法代码

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.左叶子之和

给定二叉树的根节点 root ，返回所有左叶子之和。

示例 1：

输入: root = [3,9,20,null,null,15,7]
输出: 24
解释: 在这个二叉树中，有两个左叶子，分别是 9 和 15，所以返回 24

递归法

比较常规，通过遍历检测左叶子，检测到就累加其值到引用变量中。

注意如果当前节点的左孩子是叶子节点的话，就不用往当前节点的左支递归了，把左支递归的语句写在else还会快点。

递归法代码

class Solution {
public:
    int sumOfLeftLeaves(TreeNode* root) {
        int res = 0;
        traversal(root,res);
        return res;
    }
    void traversal(TreeNode* node,int &res)
    {
        if(node->left != nullptr && node->left->left == nullptr && node->left->right == nullptr)
        {
            res += node->left->val;
        }else
        {
            if(node->left)traversal(node->left,res);
        }
        if(node->right)traversal(node->right,res);
        if( node->left== nullptr && node->right == nullptr){return;}
    }
};

还是只用一个函数的最优雅，只用一个函数就必须要用返回值了，我们可以这样设定，根节点下的左叶子数等于其子树的左叶子数之和，我们可以一路递归深入，如果碰到左叶子就返回左叶子的值，不然就返回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);
    }
};

迭代法还是遍历，然后判断，没什么好提的。