[代码随想录Day16打卡] 找树左下角的值路径总和从中序与后序遍历序列构造二叉树

🕗 发布于 2024-11-20 14:33 python 算法 开发语言

找树左下角的值

定义：二叉树中最后一行最靠左侧的值。
前序，中序，后序遍历都是先遍历左然后遍历右。
因为优先遍历左节点，所以递归中因为深度增加更新result的时候，更新的值是当前深度最左侧的值，到最后就得到了最后一行最靠左的节点。
注意：其中也有回溯，depth++; traversal(root->left,depth); depth–;这里，为什么用函数处理完之后depth要–？因为在处理完左节点的深度后，要减掉左节点的深度，然后再处理右节点的深度。
下面是C++, JAVA, Python的代码。

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    int maxDepth = INT_MIN;//int中的最小值
    int result;//记录节点的值
    void traversal(TreeNode* root, int depth){
        if(root->left == NULL && root->right == NULL){
            if(depth > maxDepth){
                maxDepth = depth;
                result = root->val;//如果深度增加就更新result保存的节点的值，因为遍历顺序是坐在右的前面所以能让result更新的一定是当前深度下的最左边的节点
            }
        }
        //然后处理左节点的值
        if(root->left){
            depth++;
            traversal(root->left, depth);
            depth--;//回溯
        }//这三行就相当于traversal(root->left, depth+1)//做了++操作但是没有改变depth的值
        if(root->right){
            depth++;
            traversal(root->right, depth);
            depth--;
        }
    }
    int findBottomLeftValue(TreeNode* root) {
       int depth = 0;
       traversal(root, depth);
       return result;
    }
};

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    private int maxDepth = -1;
    private int result;
    void traversal(TreeNode root, int depth){
        if(root.left == null && root.right==null){//碰到叶子节点了来比较当前叶子节点的深度和最大深度
            if(depth > maxDepth){
                maxDepth = depth;
                result = root.val;
            }
        }
        //处理左节点
        if(root.left!=null){
            depth++;
            traversal(root.left, depth);
            depth--;//这三行相当于traversal(root.left, depth+1)
        }
        //处理右节点
        if(root.right!=null){
            depth++;
            traversal(root.right, depth);
            depth--;//这三行相当于traversal(root.right, depth+1)
        }

    }
    public int findBottomLeftValue(TreeNode root) {
        int depth = 0;
        traversal(root, depth);
        return result;
    }
}

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution(object):
    
    def traversal(self, root, depth):
        
        if root.left==None and root.right==None:
            if depth > self.maxDepth:#如果当前深度比最大深度大，更新result的值
                self.maxDepth = depth
                self.result = root.val
        if root.left!=None:
            depth+=1
            self.traversal(root.left, depth)
            depth-=1
        if root.right!=None:
            depth+=1
            self.traversal(root.right, depth)
            depth-=1
        
    def findBottomLeftValue(self, root):
        """
        :type root: Optional[TreeNode]
        :rtype: int
        """
        self.maxDepth = -1
        self.result = None
        depth = 0
        self.traversal(root, depth)
        return self.result

参考文章

https://programmercarl.com/0513.%E6%89%BE%E6%A0%91%E5%B7%A6%E4%B8%8B%E8%A7%92%E7%9A%84%E5%80%BC.html

路径总和

在这里插入图片描述

我们在递归外面用目标值减去根节点的值得到新的目标值，这样之后不必处理中也就是节点本身，而是处理节点的左右子节点。前中后序都一样（因为没有对中进行操作，只对左右进行操作）。

确定递归函数的参数和返回值：参数node和 count，输出是bool类型。如果它遍历的一条子路径符合要求就一层一层向上返回true。
确定终止条件：因为对左右子节点进行操作，所以要避免左右子节点为空，如果为空，count为0符合要求返回True，如果左右节点为空，count不为0不符合要求，返回False。
确定单层递归的逻辑：count减去当前的left/right节点，然后放到递归函数中判断。回溯的时候count+上当前的left/right节点。
下面是C++,JAVA和Python代码。
其中也用到了回溯，再理解一遍回溯思想。在处理左右节点的时候的函数。

count-=node->left->val;
if(traversal(node->left, count)) return true;
count += node->left->val;

我看弹幕上有人说：发现这条路径最后count不是0不符合条件的情况下，需要找到别的路径，这就需要退回去找。

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    bool hasPathSum(TreeNode* root, int targetSum) {
        if(root){
            int count = targetSum-root->val;
            return traversal(root, count);
        }
        return false;
    }
    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;
    }
};

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    boolean 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!=null){
            count-=node.left.val;
            if(traversal(node.left, count)) return true;//函数中最开始进行判断
            count+=node.left.val;//回溯
        }
        if(node.right!=null){
            count-=node.right.val;
            if(traversal(node.right, count)) return true;
            count+=node.right.val;
        }
        return false;
    }
    public boolean hasPathSum(TreeNode root, int targetSum) {
        if(root!=null){
            int count = targetSum-root.val;
            return traversal(root, count);
        }
        return false;
    }
}

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution(object):
    def hasPathSum(self, root, targetSum):
        """
        :type root: Optional[TreeNode]
        :type targetSum: int
        :rtype: bool
        """
        if(root!=None):
            count=targetSum-root.val
            return self.traversal(root, count)
        return False
    def traversal(self, node, count):
        if node.left==None and node.right==None and count==0:
            return True
        if node.left==None and node.right==None and count!=0:
            return False#说明这条路径不是
        if(node.left != None):
            count -= node.left.val
            if(self.traversal(node.left, count)):
                return True
            count += node.left.val
        if(node.right != None):
            count -= node.right.val
            if(self.traversal(node.right, count)):
                return True
            count += node.right.val
        return False

路径之和Ⅱ

在这里插入图片描述

给你二叉树的根节点 root 和一个整数目标和 targetSum ，找出所有从根节点到叶子节点路径总和等于给定目标和的路径。
与上一个相比要定义vector<vector> result;存储所有的路径，vector path;存储当前路径。
下面是C++，JAVA和Python代码。

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
private:
    vector<vector<int>> result;
    vector<int> path;
    //递归函数不需要返回值，因为我们要遍历整个树
    void traversal(TreeNode* cur, int count){
        if(!cur->left && !cur->right && count == 0){//遇到了叶子节点，而且找到了和为targetSum的路径
            result.push_back(path);
            return;
        }
        if(!cur->left && !cur->right) return; //如果遇到叶子节点，没有合适的路径就直接返回

        if(cur->left){//左，防止遍历空节点
            path.push_back(cur->left->val);//从后面加入
            count -= cur->left->val;
            traversal(cur->left, count);//递归
            count += cur->left->val;//下面两个都是回溯，就是递归到这个节点和出这个节点的两种情况下环境不变
            path.pop_back();//从后面弹出
        }
        if(cur->right){//左，防止遍历空节点
            path.push_back(cur->right->val);//从后面加入
            count -= cur->right->val;
            traversal(cur->right, count);//递归
            count += cur->right->val;//下面两个都是回溯，就是递归到这个节点和出这个节点的两种情况下环境不变
            path.pop_back();//从后面弹出
        }
        return;
    }
public:
    vector<vector<int>> pathSum(TreeNode* root, int targetSum) {
        result.clear();
        path.clear();
        if(root==NULL) return result;
        path.push_back(root->val);//把根节点放到路径
        traversal(root, targetSum - root->val);
        return result;
    }
};

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {

    public List<List<Integer>> pathSum(TreeNode root, int targetSum) {
        List<List<Integer>> result = new ArrayList<>();
        if (root == null) return result; // 非空判断
        Deque<Integer> path = new LinkedList<>(); // 使用Deque
        path.add(root.val);
        traversal(root, targetSum - root.val, result, path);
        return result;
    }

    public void traversal(TreeNode root, int count, List<List<Integer>> result, Deque<Integer> path) {
        if (root.left == null && root.right == null && count == 0) {
            result.add(new ArrayList<>(path));
            return;
        }
        if (root.left == null && root.right == null) return; // 这条路径不符合要求

        if (root.left != null) { // 左子树
            path.addLast(root.left.val);
            count -= root.left.val;
            traversal(root.left, count, result, path);
            count += root.left.val;
            path.pollLast();
        }
        if (root.right != null) { // 右子树
            path.addLast(root.right.val);
            count -= root.right.val;
            traversal(root.right, count, result, path);
            count += root.right.val;
            path.pollLast();
        }
    }
}

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution(object):
    def __init__(self):
        self.result = []
        self.path = []
    def traversal(self, cur, count):
        if not cur.left and not cur.right and count == 0:#遇到了叶子节点而且找到了和为目标值的路径
            self.result.append(self.path[:])
            return 
        if not cur.left and not cur.right:#遇到了叶子节点但是路径不符合条件
            return
        if cur.left:#左 空节点不遍历
            self.path.append(cur.left.val)
            count-=cur.left.val
            self.traversal(cur.left, count)
            count += cur.left.val
            self.path.pop() #回溯
        if cur.right: #右 空节点不遍历
            self.path.append(cur.right.val)
            count -= cur.right.val
            self.traversal(cur.right, count) #递归
            count += cur.right.val #回溯
            self.path.pop() #回溯
        return
    def pathSum(self, root, targetSum):
        """
        :type root: Optional[TreeNode]
        :type targetSum: int
        :rtype: List[List[int]]
        """
        if not root:
            return self.result
        self.path.append(root.val)
        self.traversal(root, targetSum - root.val)
        return self.result

参考文章

https://programmercarl.com/0112.%E8%B7%AF%E5%BE%84%E6%80%BB%E5%92%8C.html

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

下面是C++代码。
主要的步骤有6个：

后序数组为0，说明是空节点。
后续数组最后一个元素为节点元素。
寻找中序数组位置找切割点。
切割中序数组。
切割后序数组。
递归处理左区间和右区间。

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
private:
    TreeNode* traversal (vector<int>& inorder, int inorderBegin, int inorderEnd, vector<int>& postorder, int postorderBegin, int postorderEnd){
        if (postorderBegin == postorderEnd) return NULL;

        int rootValue = postorder[postorderEnd - 1];
        TreeNode* root = new TreeNode(rootValue);

        if(postorderEnd - postorderBegin == 1) return root;
        int delimiterIndex;
        for(delimiterIndex = inorderBegin; delimiterIndex < inorderEnd; delimiterIndex++){
            if(inorder[delimiterIndex] == root->val) break;
        }
        //切割中序数组
        //左中序区间左闭右开
        int leftInorderBegin = inorderBegin;
        int leftInorderEnd = delimiterIndex;
        //右中序区间，左闭右开[rightInorderBegin, rightInorderEnd]
        int rightInorderBegin = delimiterIndex+1;
        int rightInorderEnd = inorderEnd;

        //切割后续数组
        // 左后序区间，左闭右开[leftPostorderBegin, leftPostorderEnd)
        int leftPostorderBegin =  postorderBegin;
        int leftPostorderEnd = postorderBegin + delimiterIndex - inorderBegin; // 终止位置是 需要加上 中序区间的大小size
        // 右后序区间，左闭右开[rightPostorderBegin, rightPostorderEnd)
        int rightPostorderBegin = postorderBegin + (delimiterIndex - inorderBegin);
        int rightPostorderEnd = postorderEnd - 1; // 排除最后一个元素，已经作为节点了
        root->left = traversal(inorder, leftInorderBegin, leftInorderEnd,  postorder, leftPostorderBegin, leftPostorderEnd);
        root->right = traversal(inorder, rightInorderBegin, rightInorderEnd, postorder, rightPostorderBegin, rightPostorderEnd);

        return root;
    }
public:
    TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {
       if(inorder.size()==0 || postorder.size()==0) return NULL;
       //左闭右开的原则
       return traversal(inorder, 0, inorder.size(), postorder, 0, postorder.size()); 
    }
};

参考文章

https://programmercarl.com/0112.%E8%B7%AF%E5%BE%84%E6%80%BB%E5%92%8C.html

原文地址：https://blog.csdn.net/goodenough5/article/details/143868450

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！

上一篇：linux配置动态ip
下一篇：百度遭初创企业指控抄袭，维权还是碰瓷？

Windows电脑本地部署llamafile并接入Qwen大语言模型远程AI对话实战
Windows电脑本地部署llamafile并接入Qwen大语言模型远程AI对话实战
阅读更多2024-11-23
解决vm虚拟机中ctrl键粘滞问题（一直处于按下状态）
虚拟机中点击鼠标左键没有问题，单独按下键盘也没有问题，但是如果按下键盘的同时在按下鼠标左键就会卡住。而且100%稳定复现。发现问题原因：vm版本的问题，我的版本是17.5.0，升级成17.5.2 bu
阅读更多2024-11-23
第十章 JavaScript的应用
10.1.1 JavaScript简介1 简单性JavaScript 设计之初就考虑到了非专业程序员的使用，因此它的语法相对简单，容易上手。2 动态性JavaScript 是一种解释型语言，代码可以在
阅读更多2024-11-23
非root用户安装CUDA
4.下载完成后执行.run文件，需要添加两个参数，一个是--override，用于跳过某些检查或限制；另一个是--toolkitpath，它表示安装路径，必须是自己目录下面的路径，如果是根目录就会安装
阅读更多2024-11-23
Python操作neo4j库py2neo使用之py2neo 删除及事务相关操作（三）
【代码】## Python操作neo4j库py2neo使用之py2neo 删除及事务相关操作（三）
阅读更多2024-11-23
【通俗理解】Jensen不等式与变分分布q(z)在积分计算中的应用
Jensen不等式 #变分分布 #积分计算 #期望 #凸函数 #优化问题 #下界估计 #机器学习。
阅读更多2024-11-23
「Mac玩转仓颉内测版27」基础篇7 - 字符串类型详解
本篇将介绍 Cangjie 中的字符串类型，包括字符串的定义、字面量形式、插值表达、常用操作及应用场景，帮助开发者熟练掌握字符串的使用。
阅读更多2024-11-23
数据科学与SQL：组距分组分析 | 区间分布问题
绝对值分布分析也可以理解为组距分组分析。对于某个指标而言，一个记录对应的指标值的绝对值，肯定落在所有指标值的绝对值的最小值和最大值构成的区间内，根据一定的算法，在把这个区间划分为等距离的几个小区间，，
阅读更多2024-11-23
c++编译报C1004错误的原因及解决办法
可能是你的代码文件最后没有正确的结束符，或者是缺少了一些必要的头文件或语句。默认磁盘驱动器没有足够的空间用于临时文件，需要大约两倍于源文件的空间。编译器到达了源文件尾但未解析构造。计算结果为假的 #i
阅读更多2024-11-23
mysql 去重补全取出重复变量函数和存储过程
mysql 去重补全取出重复变量函数和存储过程
阅读更多2024-11-23

[代码随想录Day16打卡] 找树左下角的值 路径总和 从中序与后序遍历序列构造二叉树

找树左下角的值

参考文章

路径总和

路径之和Ⅱ

参考文章

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

参考文章

相关文章

[代码随想录Day16打卡] 找树左下角的值路径总和从中序与后序遍历序列构造二叉树