Day14 | 找树左下角的值 路径总和 从中序与后序遍历序列构造二叉树

语言

Java

找树左下角的值

题目链接：找树左下角的值

题目

给定一个二叉树的 根节点 root，请找出该二叉树的 最底层 最左边 节点的值。

假设二叉树中至少有一个节点。

思路

本题有两种做法我主要讲一下递归的思路，创建两个全局变量，一个用于存树的深度，一个用于记录最下层最左树的值depth。

递归终止条件：树的左右子树都为空。 递归参数：节点，深度。

单层递归：先判断左右子树是否为空，为空了代表下面没有子树了，这时比较当前深度和全局变量的深度哪个大，当前深度大的话赋值给全局变量，也把值赋值给depth.然后判断左子树是否为空不为空的话进行递归，需要进行回溯操作。右子树同理。具体细节看代码。

代码

递归法

class Solution {
    int Deep = -1;
    int value = 0;//全局变量记录左下角的值
    public int findBottomLeftValue(TreeNode root) {
        findLeftValue(root, 0);
        return value;
    }
    public void findLeftValue(TreeNode root, int deep) {
        if (root.left == null && root.right == null) {
            if (deep > Deep) {
                Deep = deep;
                value = root.val;
            }
        }
        if (root.left != null) {
            deep++;
            findLeftValue(root.left, deep);
            deep--;
        }
        if (root.right != null) {//回溯
            deep++;
            findLeftValue(root.right, deep);
            deep--;
        }
    }
}

迭代法

class Solution {
    public int findBottomLeftValue(TreeNode root) {
        Queue<TreeNode> que = new LinkedList<>();
        int res = 0;
        que.offer(root);
        while (!que.isEmpty()) {
            int len = que.size();
            for (int i = 0; i < len; i++) {
                TreeNode tempNode = que.poll();
                if (i == 0) {
                    res = tempNode.val;
                }
                if (tempNode.left != null) {
                    que.offer(tempNode.left);
                }
                if (tempNode.right != null) {
                    que.offer(tempNode.right);
                }
            }
        }
        return res;
    }
}

易错点

递归法时要注意全局变量，还有回溯的过程。

路径总和

题目链接：路径之和

题目链接113. 路径总和ii

题目

给你二叉树的根节点 root 和一个表示目标和的整数 targetSum 。判断该树中是否存在 根节点到叶子节点 的路径，这条路径上所有节点值相加等于目标和 targetSum 。如果存在，返回 true ；否则，返回 false 。

叶子节点 是指没有子节点的节点。

思路

采用递归的方法，传入的值是targetSum，对它进行减减，如果节点的左右子树都为空且targetsum为0返回TRUE，分别向左和右递归，最后没找到的话返回false.

代码

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

易错点

先判断根节点是否为空再进行减减操作。

扩展

做完路径之和后，二也就会做了。不用返回true了，是将所有路径都遍历一遍。找出符合的

class Solution {
    public List<List<Integer>> pathSum(TreeNode root, int targetSum) {
        List<List<Integer>> res = new ArrayList<>();//结果数组
        if (root == null) return res;//非空判断

        List<Integer> path = new LinkedList<>();
        traversal(root, targetSum, res, path);
        return res;
    }
    public void traversal(TreeNode root, int targetSum, List<List<Integer>> res,List<Integer> path) {
        path.add(root.val);
        if (root.left == null && root.right == null) {
            if (targetSum - root.val == 0) {
                res.add(new ArrayList(path));
            }
            return;
        }
        if (root.left != null) {
            traversal(root.left, targetSum - root.val, res, path);
            path.remove(path.size() - 1);//回溯
        }
        if (root.right != null) {
            traversal(root.right, targetSum - root.val, res, path);
            path.remove(path.size() - 1);
        }
    } 
}

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

题目链接：从中序和后序遍历构造函数

题目

给定两个整数数组 inorder 和 postorder ，其中 inorder 是二叉树的中序遍历， postorder 是同一棵树的后序遍历，请你构造并返回这颗 二叉树 。

思路

用一个Map存经过中序数组遍历出值和索引，开始递归

从后序遍历中找出根节点也就是最后一个，在中序遍历中找到它的索引。

开始切割根节点左边的是左子树，右边的是右子树。

代码

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.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 lenLeftOf = rootIndex - inBegin;
        root.left = findNode(inorder, inBegin, rootIndex, postorder, postBegin, postBegin + lenLeftOf);
        root.right = findNode(inorder, rootIndex + 1, inEnd, postorder, postBegin + lenLeftOf, postEnd - 1);
        return root;
    }
}

易错点

递归右子树的参数传递，后序遍历的时候无需在遍历最后一个节点了。

扩展

做完中序和后序，下面试一试前序和中序。

class Solution {
    Map <Integer, Integer> map;
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        map = new HashMap<>();
        for (int i = 0; i < inorder.length; i++) {
            map.put(inorder[i], i);
        }
        return findNode(inorder, 0 ,inorder.length, preorder, 0, preorder.length);
    }
    public TreeNode findNode(int[] inorder, int inBegin, int inEnd, int[] preorder, int preBegin, int preEnd) {
        if (inBegin >= inEnd || preBegin >= preEnd) {
            return null;
        }
        int rootIndex = map.get(preorder[preBegin]);
        TreeNode root = new TreeNode(inorder[rootIndex]);
        int lenLeftOf = rootIndex - inBegin;
        root.left = findNode(inorder, inBegin, rootIndex, preorder, preBegin + 1, preBegin + lenLeftOf + 1);
        root.right = findNode(inorder, rootIndex + 1, inEnd, preorder, preBegin + lenLeftOf + 1, preEnd);
        return root;
    }
}

 

原文地址：https://blog.csdn.net/q864508127/article/details/140513177

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