.leetcode(112. Path Sum)

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

 

2. 2022/05/12 시도

소요시간: 8분(recursive-topdown), 8분(iterative-dfs)

// recursive-topdown
class Solution {
    boolean hasAnswer = false;
    int targetSum;
    public boolean hasPathSum(TreeNode root, int targetSum) {
        if (root == null) {
            return false;
        }

        this.targetSum = targetSum;
        recursive(root, 0);
        return hasAnswer;
    }
    
    private void recursive(TreeNode root, int sum) {
        if (hasAnswer) {
            return;
        }

        if (root.left == null && root.right == null && targetSum == sum + root.val) {
            hasAnswer = true;
            return;
        }

        if (root.left != null) {
            recursive(root.left, sum + root.val);
        }

    if (root.right != null) {
            recursive(root.right, sum + root.val);
        }
    }
}

// iterative-dfs
class Solution {
    public boolean hasPathSum(TreeNode root, int targetSum) {
        if (root == null) {
            return false;
        }
        
        Stack<TreeNode[]> stack = new Stack<>();
        stack.push(new TreeNode[]{root, new TreeNode(root.val)});
        
        while (!stack.isEmpty()) {
            TreeNode[] nodes = stack.pop();
            TreeNode onode = nodes[0];
            TreeNode snode = nodes[1];
            
            if (onode.left == null && onode.right == null && snode.val == targetSum) {
                return true;
            }
            
            if (onode.left != null) {
                stack.push(new TreeNode[]{onode.left, new TreeNode(snode.val + onode.left.val)});
            }
            
            if (onode.right != null) {
                stack.push(new TreeNode[]{onode.right, new TreeNode(snode.val + onode.right.val)});
            }
        }

        return false;               
    }
}

// iterative-bfs
class Solution {
    public boolean hasPathSum(TreeNode root, int targetSum) {
        if (root == null) {
            return false;
        }
        
        Queue<TreeNode[]> queue = new LinkedList<>();
        queue.offer(new TreeNode[]{root, new TreeNode(root.val)});
        
        while (!queue.isEmpty()) {
            TreeNode[] nodes = queue.poll();
            TreeNode onode = nodes[0];
            TreeNode snode = nodes[1];
            
            if (onode.left == null && onode.right == null && snode.val == targetSum) {
                return true;
            }
            
            if (onode.left != null) {
                queue.offer(new TreeNode[]{onode.left, new TreeNode(snode.val + onode.left.val)});
            }
            
            if (onode.right != null) {
                queue.offer(new TreeNode[]{onode.right, new TreeNode(snode.val + onode.right.val)});
            }
        }

        return false;               
    }
}

풀이 접근 과정

recursive-topdown
iterative-dfs
iterative-bfs

 

느낀점

• recursive-bottomup은 이번에 생각하지 못했다. 아래 첫번째 시도에서 처럼 하면 bottomup으로도 풀 수 있다.

---

1. 2022.01.16 시도

소요시간: 6분(recursive), 4분(iterative)

// recursive-buttomup
class Solution {
    public boolean hasPathSum(TreeNode root, int targetSum) {
        if (root == null) {
            return false;
        }
        
        if (root.left == null && root.right == null) {
            if (root.val == targetSum) {
                return true;
            }
            return false;
        }

        int nextTargetSum = targetSum-root.val;
        boolean result1 = hasPathSum(root.left, nextTargetSum);
        boolean result2 = hasPathSum(root.right, nextTargetSum);
        return result1 || result2;
    }
}

// iterative-dfs
class Solution {
    public boolean hasPathSum(TreeNode root, int targetSum) {
        if (root == null) {
            return false;
        }
        
        LinkedList<TreeNode> stack = new LinkedList<>();
        stack.push(root);
        
        while(!stack.isEmpty()) {
            TreeNode node = stack.pop();
               
            if (node.left == null && node.right == null) {
                if (node.val == targetSum) {
                    return true;
                }
            }
            
            if (node.left != null) {
                node.left.val += node.val;
                stack.push(node.left);
            }
            
            if (node.right != null) {
                node.right.val += node.val;
                stack.push(node.right);
            }
        }
     
        return false;
    }
}

풀이 접근 과정

이전에 많이 풀던 방식(TreeNode)으로 tree는 recursive, iterative방식으로 풀어보면 되겠다 싶었다. recursive할때는 재귀가 될때마다 지금 현재 값을 마이너스해서 노드값하고 비교하면 된다고 생각했다.

iterative에서는 반대로 노드에 값을 더해가면서 targetSum과 비교할 수 있게 하였다.

 

느낀점

• 크게 어려운점은 없었다.

---

알고리즘 정리노트: .leetcode(알고리즘 문제풀이 접근)

반응형