LeetCode112

非商业，LeetCode链接附上：

https://leetcode-cn.com/problems/path-sum/

进入正题。

题目：

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

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

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

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

代码实现：

1//节点
2class TreeNode {
3        int val;
4        TreeNode left;
5        TreeNode right;
6  
7        public TreeNode(int val) {
8            this.val = val;
9        }
10}
11
12//方法一 递归
13public boolean hasPathSum(TreeNode root, int sum) {
14
15        if(root == null) {
16            return false;
17        }
18        
19        if(root.left == null && root.right == null) {
20            return root.val == sum;
21        }
22        
23        return hasPathSum(root.left, sum - root.val) || hasPathSum(root.right, sum - root.val);
24}
25//时间复杂度O(n)，空间复杂度：O(H)，其中 H 是树的高度。
26
27//方法二 迭代
28public boolean hasPathSum(TreeNode root, int sum) {
29
30        if(root == null) {
31            return false;
32        }
33        Queue<TreeNode> queNode = new LinkedList<>();
34        Queue<Integer> queVal = new LinkedList<>();
35        queNode.offer(root);
36        queVal.offer(root.val);
37        
38        while (!queNode.isEmpty()) {
39            
40            TreeNode node = queNode.poll();
41            int temp = queVal.poll();
42            
43            if(node.left == null && node.right == null) {
44                if(sum == temp) {
45                    return true;
46                }
47                continue;
48            }
49            
50            if(node.left != null) {
51                queNode.offer(node.left);
52                queVal.offer(node.left.val + temp);
53            }
54            if(node.right != null) {
55                queNode.offer(node.right);
56                queVal.offer(node.right.val + temp);
57            }
58        }
59        
60        return false;
61}
62//时间复杂度O(n)，空间复杂度O(n)

分析：

递归的方法，判断终止条件，并逐渐缩小问题规模；

迭代的方法，初始化一个队列(Queue)，记录到每一个节点对应的路径值。

--End

本文同步分享在 博客"黑冰台"（CNBlog）。
如有侵权，请联系 support@oschina.cn 删除。
本文参与“OSC源创计划”，欢迎正在阅读的你也加入，一起分享。