Session 29: Binary Trees 3

Original Session

Date: 11 Jan 2025

Topic: Trees

Concept: Height of Binary Tree = max(left, right) + 1

Programs

1. 113. Path Sum II
   1. leetcode here

   class Solution {
   
       List<List<Integer>> listPath = new ArrayList();
       public List<List<Integer>> pathSum(TreeNode root, int targetSum) {
           
           func(root,targetSum, new ArrayList());
           return listPath;
       }
   
       void func(TreeNode root, int targetSum, List<Integer> list) {
   
           if (root != null) {
   
               list.add(root.val);
   
               if (root.left == null && root.right == null && root.val == targetSum) {
                   listPath.add(new ArrayList(list));
               }
   
               func(root.left, targetSum - root.val, list);
               func(root.right, targetSum - root.val, list);
               list.remove(list.size() - 1);
           }
       }
   }

2. [Someone Got these questions in Interview]
   1. leetcode here

   1. https://www.geeksforgeeks.org/maximize-absolute-displacement-from-origin-by-moving-on-x-axis-based-on-given-commands/
   2. https://leetcode.com/problems/simplify-path/description/

3. 437. Path Sum III
   1. leetcode here

   HashMap<Long, Integer> sumCount = new HashMap<>();
       int result = 0;
   
       public int pathSum(TreeNode root, int targetSum) {
           if(root == null) {
               return 0;
           }
           sumCount.put(0L, 1);
           countPaths(root, 0L, targetSum);
           return result;
       }
   
       public void countPaths(TreeNode root, Long sum, int target) {
           if(root == null) {
               return;
           }
   
           sum += root.val;
           result += sumCount.getOrDefault(sum - target, 0);
   
           sumCount.put(sum, sumCount.getOrDefault(sum, 0) + 1);
           
           countPaths(root.left, sum, target);
           countPaths(root.right, sum, target);
       
           sumCount.put(sum, sumCount.get(sum) - 1);
       }

4. 124. Binary Tree Maximum Path Sum
   1. leetcode here

   class Solution {
   
       int ans;
       public int maxPathSum(TreeNode root) {
           
           ans = Integer.MIN_VALUE;
           dfs(root);
           return ans;
       }
   
       int dfs(TreeNode root) {
   
           if (root == null) {
               return 0;
           }
   
           int lSum = Math.max(dfs(root.left), 0);
           int rSum = Math.max(dfs(root.right), 0);
           int currSum = lSum + rSum + root.val;
   
           ans = Math.max(ans, lSum + rSum + root.val);
           return Math.max(lSum + root.val, rSum + root.val);
       }
   }

5. 236. Lowest Common Ancestor of a Binary Tree
   1. leetcode here

   class Solution {
       public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
           
           if (root == null) {
               return null;
           }
   
           if (root == p || root == q) {
               return root;
           }
   
           TreeNode left = lowestCommonAncestor(root.left, p, q);
           TreeNode right = lowestCommonAncestor(root.right, p, q);
   
           if (left != null && right != null) {
               return root;
           }
   
           if (left != null) {
               return left;
           }
   
           if (right != null) {
               return right;
           }
   
           return null;
       }
   }

6. HomeWork Questions
   1. leetcode

   116, 117, 105, 226, 863, 114, 2385