代码随想录训练营day18

2024-03-29 21:14:01
开发
15

第六章二叉树 part05

1.LeetCode.找树左下角的值

1.2思路：本题要找出树的最后一行的最左边的值。此时大家应该想起用层序遍历是非常简单的了，反而用递归的话会比较难一点；如果使用递归法，如何判断是最后一行呢，其实就是深度最大的叶子节点一定是最后一行；那么如何找最左边的呢？可以使用前序遍历（当然中序，后序都可以，因为本题没有中间节点的处理逻辑，只要左优先就行），保证优先左边搜索，然后记录深度最大的叶子节点，此时就是树的最后一行最左边的值。

1.3附加代码如下所示：

（1）递归法

//递归法 
class Solution {
public:
    int maxdepth=INT_MIN;
    int result;
    void traversal(TreeNode*node,int depth)
    {
      
        //终止条件
        if(node->left==NULL&&node->right==NULL)//当遇到叶子节点的时候，就需要统计一下最大的深度了，所以需要遇到叶子节点来更新最大深度
        {
            if(depth>maxdepth)
            {
                maxdepth=depth;
                result=node->val;
            }
            return;
        }
        if(node->left)//左
        {
            depth++;
            traversal(node->left,depth);
            depth--;//回溯
        }
        if(node->right)//右
        {
            depth++;
            traversal(node->right,depth);
            depth--;
        }
        return;
    }
    int findBottomLeftValue(TreeNode* root) {
        traversal(root,1);
        return result;

    }
};

（2）迭代法

//迭代法 层序遍历
class Solution {
public:
    int findBottomLeftValue(TreeNode* root) {
        queue<TreeNode*>que;
        if(root!=NULL)que.push(root);
        int result=0;
        while(!que.empty())
        {
            int size=que.size();
            for(int i=0;i<size;i++)
            {
                TreeNode*node=que.front();
                que.pop();
                if(i==0)result=node->val;//一直遍历到最后一行的第一个节点就是二叉树的左下角的值
                if(node->left)que.push(node->left);
                if(node->right)que.push(node->right);
            }
            
            
            

        }
        return result;

    }
};

2.LeetCode. 路径总和

2.1题目链接：112. 路径总和

文章讲解：代码随想录
视频讲解：B站卡哥视频

2.2思路：可以使用深度优先遍历的方式（本题前中后序都可以，无所谓，因为中节点也没有处理逻辑）来遍历二叉树，

再来看返回值，递归函数什么时候需要返回值？什么时候不需要返回值？这里总结如下三点：

如果需要搜索整棵二叉树且不用处理递归返回值，递归函数就不要返回值。（这种情况就是本文下半部分介绍的113.路径总和ii）

如果需要搜索整棵二叉树且需要处理递归返回值，递归函数就需要返回值。（这种情况我们在236. 二叉树的最近公共祖先 (opens new window)中介绍）

如果要搜索其中一条符合条件的路径，那么递归一定需要返回值，因为遇到符合条件的路径了就要及时返回。（本题的情况）

确定递归函数的参数和返回类型
参数：需要二叉树的根节点，还需要一个计数器，这个计数器用来计算二叉树的一条边之和是否正好是目标和，计数器为int型。
而本题我们要找一条符合条件的路径，所以递归函数需要返回值，及时返回，那么返回类型是什么呢？

如图所示：
在这里插入图片描述

2.3附加代码如下所示：

（1）路径总和

//迭代法
class Solution {
public:
    bool hasPathSum(TreeNode* root, int targetSum) {
        // 此时栈里要放的是pair<节点指针，路径数值>
        stack<pair<TreeNode*,int>>stk;//保存树的遍历节点,用pair<TreeNode*,int>及保存遍历的树节点又能吧遍历的路径数值之和存放起来
        
        if(root==NULL)return false;
        stk.push(pair<TreeNode*,int>(root,root->val));
      
        while(!stk.empty())
        {
            pair<TreeNode*,int> node=stk.top(); stk.pop();
            // 如果该节点是叶子节点了，同时该节点的路径数值等于sum，那么就返回true
            if(node.first->left==NULL&&node.first->right==NULL&&targetSum==node.second)
            {
                return true;
            }

            if(node.first->left)//左
            {
                stk.push(pair<TreeNode*,int>(node.first->left,node.second+node.first->left->val));
               
            }
            if(node.first->right)//右
            {
                stk.push(pair<TreeNode*,int>(node.first->right,node.second+node.first->right->val));
            }

        }
        return false;

    }
};

//递归法 
class Solution {
public:
    bool traversal(TreeNode*node,int count)
    {
        
        //终止条件
        if(node->left==NULL&&node->right==NULL&&count==0)
        {
            return true;
        }
        if(node->left==NULL&&node->right==NULL&&count!=0)
        {
            return false;
        }

        if(node->left)//左
        {
            count-=node->left->val;
            if(traversal(node->left,count))return true;
            count+=node->left->val;
        }
        if(node->right)//右
        {
            count-=node->right->val;
            if(traversal(node->right,count))return true;
            count+=node->right->val;

        }
        return false;
    }
    bool hasPathSum(TreeNode* root, int targetSum) {
        if(root==NULL)return false;
        return traversal(root,targetSum-root->val);
        
    }
};

（2）路径总和Ⅱ

class Solution {
private:
    vector<vector<int>>result;
    vector<int>path;
    // 递归函数不需要返回值，因为我们要遍历整个树
    void traversal(TreeNode*node,int count)
    {
        //终止条件
        if(node->left==NULL&&node->right==NULL&&count==0)
        {
            result.push_back(path);
            return;
        }
        if(node->left==NULL&&node->right==NULL&&count!=0)return;

        if(node->left)//左
        {
            count-=node->left->val;
            path.push_back(node->left->val);
            traversal(node->left,count);
            count+=node->left->val;//计数值回溯
            path.pop_back();//路径节点值回溯
        }
        if(node->right)//右
        {
            count-=node->right->val;
            path.push_back(node->right->val);
            traversal(node->right,count);
            count+=node->right->val;//计数值回溯
            path.pop_back();//路径节点值回溯

        }
    }

public:

    vector<vector<int>> pathSum(TreeNode* root, int targetSum) {
        result.clear();//如果Solution类的实例只被使用一次，那么这两行代码可以省略，因为result和path在每次创建Solution类的新实例时都会是空的。
        path.clear();//这两行代码是为了清楚之前调用该函数的执行结果
        if(root==NULL)return result;
        path.push_back(root->val);//把根节点放进去
        traversal(root,targetSum-root->val);
        return result;

    }
};

3.LeetCode.从中序与后序遍历序列构造二叉树

3.2思路：以后序数组的最后一个元素为切割点，先切中序数组，根据中序数组，反过来再切后序数组。一层一层切下去，每次后序数组最后一个元素就是节点元素。注意采用前序遍历和后序遍历是不能得到完整二叉树的（具体可以自己画图一目了然）。

整体思路步骤：
说到一层一层切割，就应该想到了递归。

来看一下一共分几步：

第一步：如果数组大小为零的话，说明是空节点了。

第二步：如果不为空，那么取后序数组最后一个元素作为节点元素。

第三步：找到后序数组最后一个元素在中序数组的位置，作为切割点

第四步：切割中序数组，切成中序左数组和中序右数组（顺序别搞反了，一定是先切中序数组）

第五步：切割后序数组，切成后序左数组和后序右数组

第六步：递归处理左区间和右区间

3.3附加代码如下所示：

//递归法 
class Solution {
public:
    TreeNode*traversal(vector<int>& inorder, vector<int>& postorder)
    {
        if(postorder.size()==0)return NULL;
        int rootvalue=postorder[postorder.size()-1];
        TreeNode*root=new TreeNode(rootvalue);//找到根节点

        int index;
        for(index=0;index<inorder.size();index++)
        {
            if(inorder[index]==rootvalue)break;//找到中序数组切割点
        }

        //切割中序遍历数组为左中序和右中序
        vector<int>leftinorder(inorder.begin(),inorder.begin()+index);
        vector<int>rightinorder(inorder.begin()+index+1,inorder.end());

        postorder.resize(postorder.size()-1);//重新定义后续数组的大小，因为要把之前的根节点去掉
        //切割后序遍历数组为左后序和右后序
        vector<int>leftpostorder(postorder.begin(),postorder.begin()+leftinorder.size());
        vector<int>rightpostorder(postorder.begin()+leftinorder.size(),postorder.end());

        root->left=traversal(leftinorder,leftpostorder);//左子树
        root->right=traversal(rightinorder,rightpostorder);//右子树
        return root;
    }
       
    TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {
        if(postorder.size()==0||inorder.size()==0)return NULL;
        return  traversal(inorder,postorder);

    }
};

原文地址:https://blog.csdn.net/chaizihao111/article/details/136974093 本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：https://www.suanlizi.com/kf/1773700138758443008.html 如若内容造成侵权/违法违规/事实不符，请联系《酸梨子》网邮箱：1419361763@qq.com进行投诉反馈，一经查实，立即删除！

阅读全部