代码随想录Day27

标签：return Day27 随想录 节点 targetsum path null root 代码

LeetCode112. 路径总和

给定一个二叉树和一个目标和，判断该树中是否存在根节点到叶子节点的路径，这条路径上所有节点值相加等于目标和。

说明: 叶子节点是指没有子节点的节点。

示例:  给定如下二叉树，以及目标和 sum = 22

 

 返回 true, 因为存在目标和为 22 的根节点到叶子节点的路径 5->4->11->2

 

思路：从根节点一层一层的往下遍历，找到和为目标值的路径直接返回true即可。

　　遍历顺序随意选择，因为只需要遍历所有节点，中节点在何时处理都可以。

采用递归的方法：

我们可以把目标值当做初始参数传入，然后通过累减慢慢减去，最后为0时返回true。

由于返回的是true，注意回溯的时候要一直带着返回的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;
    }
}

// lc112 简洁方法
class solution {
    public boolean haspathsum(treenode root, int targetsum) {
        
        if (root == null) return false; // 为空退出
        
        // 叶子节点判断是否符合
        if (root.left == null && root.right == null) return root.val == targetsum;

        // 求两侧分支的路径和
        return haspathsum(root.left, targetsum - root.val) || haspathsum(root.right, targetsum - root.val);
    }
}

class solution {
    public boolean haspathsum(treenode root, int targetsum) {
        if(root==null)return false;
        stack<treenode> stack1 = new stack<>();
        stack<integer> stack2 = new stack<>();
        stack1.push(root);stack2.push(root.val);
        while(!stack1.isempty()){
            int size = stack1.size();
            for(int i=0;i<size;i++){
                treenode node = stack1.pop();int sum=stack2.pop();
                // 如果该节点是叶子节点了，同时该节点的路径数值等于sum，那么就返回true
                if(node.left==null && node.right==null && sum==targetsum)return true;
                // 右节点，压进去一个节点的时候，将该节点的路径数值也记录下来
                if(node.right!=null){
                    stack1.push(node.right);stack2.push(sum+node.right.val);
                }
                // 左节点，压进去一个节点的时候，将该节点的路径数值也记录下来
                if(node.left!=null){
                    stack1.push(node.left);stack2.push(sum+node.left.val);
                }
            }
        }
        return false;
    }   
    
}

 

LeetCode113.路径总和II

给定一个二叉树和一个目标和，找到所有从根节点到叶子节点路径总和等于给定目标和的路径。

说明: 叶子节点是指没有子节点的节点。

示例: 给定如下二叉树，以及目标和 sum = 22，

 

 

 本题要求和112不同，返回路径值，所以返回值为void即可。不需要具体的返回值。在操作中对保存路径的集合进行操作即可。

代码如下：

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<>();
        preorderdfs(root, targetsum, res, path);
        return res;
    }

    public void preorderdfs(TreeNode root, int targetsum, List<List<Integer>> res, List<Integer> path) {
        path.add(root.val);
        // 遇到了叶子节点
        if (root.left == null && root.right == null) {
            // 找到了和为 targetsum 的路径
            if (targetsum - root.val == 0) {
                res.add(new ArrayList<>(path));
            }
            return; // 如果和不为 targetsum，返回
        }

        if (root.left != null) {
            preorderdfs(root.left, targetsum - root.val, res, path);
            path.remove(path.size() - 1); // 回溯
        }
        if (root.right != null) {
            preorderdfs(root.right, targetsum - root.val, res, path);
            path.remove(path.size() - 1); // 回溯
        }
    }
}

// 解法2
class Solution {
    List<List<Integer>> result;
    LinkedList<Integer> path;
    public List<List<Integer>> pathSum (TreeNode root,int targetSum) {
        result = new LinkedList<>();
        path = new LinkedList<>();
        travesal(root, targetSum);
        return result;
    }
    private void travesal(TreeNode root,  int count) {
        if (root == null) return;
        path.offer(root.val);
        count -= root.val;
        if (root.left == null && root.right == null && count == 0) {
            result.add(new LinkedList<>(path));
        }
        travesal(root.left, count);
        travesal(root.right, count);
        path.removeLast(); // 回溯
    }
}

 

 

标签：return,Day27,随想录,节点,targetsum,path,null,root,代码
From： https://www.cnblogs.com/dwj-ngu/p/16906457.html