Java算法训练第十二天

题库一、翻转二叉树

递归解法 二、路径总和

递归解法 总结

给你一棵二叉树的根节点 root ，翻转这棵二叉树，并返回其根节点。
原题

运用递归思维，题目可以从叶子结点开始翻转，但访问到的结点是叶子结点时则不做任何操作。
代码如下：

    public TreeNode invertTree(TreeNode root) {
        if(root == null)
            return root;
        TreeNode left = invertTree(root.left);
        TreeNode right = invertTree(root.right);
        root.left = right;
        root.right = left;
        return root;
    }

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

运用递归思维，把参数 targetSum 作为当前达成目标需要的数值，当访问到叶子结点时则判断叶子结点的值与 targetSum 是否相等，相等则返回true,反之返回false。
代码如下：

    public boolean hasPathSum(TreeNode root, int targetSum) {
        if(root == null)
            return false;
        if(root.left == null && root.right == null)
            return targetSum == root.val;
        return hasPathSum(root.left,targetSum - root.val) || hasPathSum(root.right,targetSum - root.val);
    }