代码随想录算法训练营Day18|513.找树左下角的值、112. 路径总和、106.从中序与后序遍历序列构造二叉树

发布时间:2024年01月14日


一、513.找树左下角的值

题目描述: 给定一个二叉树,在树的最后一行找到最左边的值。

1.递归法

  1. 确定递归函数的参数和返回值
    参数必须有要遍历的树的根节点,还有就是一个int型的变量用来记录最长深度。 这里就不需要返回值了,所以递归函数的返回类型为void。
  2. 确定终止条件
    当遇到叶子节点的时候,就需要统计一下最大的深度了,所以需要遇到叶子节点来更新最大深度。
  3. 确定单层递归的逻辑
    在找最大深度的时候,递归的过程中依然要使用回溯
class Solution {
    private int Deep = -1;
    private int value = 0;
    public int findBottomLeftValue(TreeNode root) {
        value = root.val;
        findLeftValue(root,0);
        return value;
    }

    private void findLeftValue (TreeNode root,int deep) {
        if (root == null) return;
        if (root.left == null && root.right == null) {
            if (deep > Deep) {
                value = root.val;
                Deep = deep;
            }
        }
        if (root.left != null) findLeftValue(root.left,deep + 1);
        if (root.right != null) findLeftValue(root.right,deep + 1);
    }
}

二、112. 路径总和

题目描述: 给定一个二叉树和一个目标和,判断该树中是否存在根节点到叶子节点的路径,这条路径上所有节点值相加等于目标和。
说明: 叶子节点是指没有子节点的节点。

1.递归法

  1. 确定递归函数的参数和返回类型
    参数:需要二叉树的根节点,还需要一个计数器,这个计数器用来计算二叉树的一条边之和是否正好是目标和,计数器为int型。
  2. 确定终止条件
    不要去累加然后判断是否等于目标和,那么代码比较麻烦,可以用递减,让计数器count初始为目标和,然后每次减去遍历路径节点上的数值。
    如果最后count == 0,同时到了叶子节点的话,说明找到了目标和。
    如果遍历到了叶子节点,count不为0,就是没找到。
  3. 确定单层递归的逻辑
    因为终止条件是判断叶子节点,所以递归的过程中就不要让空节点进入递归了。
    递归函数是有返回值的,如果递归函数返回true,说明找到了合适的路径,应该立刻返回。
class solution {
   public boolean haspathsum(treenode root, int targetsum) {
        if (root == null) {
            return false;
        }
        targetsum -= root.val;
        // 叶子结点
        if (root.left == null && root.right == null) {
            return targetsum == 0;
        }
        if (root.left != null) {
            boolean left = haspathsum(root.left, targetsum);
            if (left) {// 已经找到
                return true;
            }
        }
        if (root.right != null) {
            boolean right = haspathsum(root.right, targetsum);
            if (right) {// 已经找到
                return true;
            }
        }
        return false;
    }
}

三、106.从中序与后序遍历序列构造二叉树

题目描述: 根据一棵树的中序遍历与后序遍历构造二叉树。
注意: 你可以假设树中没有重复的元素。

1.递归法

  1. 如果数组大小为零的话,说明是空节点了。
  2. 如果不为空,那么取后序数组最后一个元素作为节点元素。
  3. 找到后序数组最后一个元素在中序数组的位置,作为切割点。
  4. 割中序数组,切成中序左数组和中序右数组 (顺序别搞反了,一定是先切中序数组)。
  5. 切割后序数组,切成后序左数组和后序右数组。
  6. 递归处理左区间和右区间。

在这里插入图片描述

class Solution {
    Map<Integer, Integer> map;  // 方便根据数值查找位置
    public TreeNode buildTree(int[] inorder, int[] postorder) {
        map = new HashMap<>();
        for (int i = 0; i < inorder.length; i++) { // 用map保存中序序列的数值对应位置
            map.put(inorder[i], i);
        }

        return findNode(inorder,  0, inorder.length, postorder,0, postorder.length);  // 前闭后开
    }
    
    public TreeNode findNode(int[] inorder, int inBegin, int inEnd, int[] postorder, int postBegin, int postEnd) {
        // 参数里的范围都是前闭后开
        if (inBegin >= inEnd || postBegin >= postEnd) {  // 不满足左闭右开,说明没有元素,返回空树
            return null;
        }
        int rootIndex = map.get(postorder[postEnd - 1]);  // 找到后序遍历的最后一个元素在中序遍历中的位置
        TreeNode root = new TreeNode(inorder[rootIndex]);  // 构造结点
        int lenOfLeft = rootIndex - inBegin;  // 保存中序左子树个数,用来确定后序数列的个数
        root.left = findNode(inorder, inBegin, rootIndex,
                            postorder, postBegin, postBegin + lenOfLeft);
        root.right = findNode(inorder, rootIndex + 1, inEnd,
                            postorder, postBegin + lenOfLeft, postEnd - 1);

        return root;
    }
}

文章来源:https://blog.csdn.net/qq_41929830/article/details/135580329
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。