# Leetcode Tree traverse, DFS, BFS (BinaryTree traverse, preorder, inorder, postorder, bfs, bfs storing level) Problems by type DFS (Visit friends, numIslands, Valid binary search tree) Sliding Window (minWindow, lengthOfLongestSubstring, checkInclusion) BackTracking (subsets, combinationSum, permutations) Dynamic (longestPalindrome, maxProfit, maxSubArray) ## Tree traverse, DFS, BFS DFS (Depth First Search): Pre, in and postorder are variations of DFS ### Binary tree traverse ```php class BinaryNode1 { public $data; public $left; public $right; public function __construct(string $data = NULL) { $this->data = $data; $this->left = NULL; $this->right = NULL; } public function addChildren(BinaryNode1 $left, BinaryNode1 $right) { $this->left = $left; $this->right = $right; } } class BinaryTree { public $root = NULL; public function __construct(BinaryNode1 $node) { $this->root = $node; } public function traverse(BinaryNode1 $node, int $level = 0) { if ($node) { echo str_repeat("-", $level); echo $node->data . "\n"; if ($node->left) $this->traverse($node->left, $level + 1); if ($node->right) $this->traverse($node->right, $level + 1); } } } ``` ### Binary tree DFS (pro, in, post) DFS using stack: 1. $stack[] = $root; 2. $node = $stack->pop(); 3. Fetch its unvisited neighbours $stack->push($current->right); $stack->push($current->left); 4. Repeat 2,3 until stack empty. ```php class BinaryNode { public $value; public $left; public $right; public function __construct($item) { $this->value = $item; $this->left = null; $this->right = null; } public function isEmpty() {} public function insert($item) {} protected function insertNode($node, &$subtree) {} } class TraversalBT { public function preOrderTraversal(BinaryNode $root) { $preOrder = []; $nodes = new SplStack(); if ($root == null) { return $preOrder;} while ($root !== null || !$nodes->isEmpty()) { while ($root !== null) { $preOrder[] = $root->value; $nodes->push($root); $root = $root->left; } $root = $nodes->pop(); $root = $root->right; } return $preOrder; } public function inorderTraversal(BinaryNode $root) { $inorder = []; $nodes = new SplStack(); if ($root == null) {return $inorder;} while ($root !== null || !$nodes->isEmpty()) { while ($root !== null) { $nodes->push($root); $root = $root->left; } $root = $nodes->pop(); $inorder[] = $root->value; $root = $root->right; } return $inorder; } public function postOrderTraversal(BinaryNode $root) { $postOrder, $visited = []; $nodes = new SplStack(); if ($root == null) { return $postOrder; } while ($root !== null || !$nodes->isEmpty()) { while ($root !== null) { $nodes->push($root); $root = $root->left; } $root = $nodes->pop(); if ($root->right !== null && !in_array($root, $visited)) { $nodes->push($root); $visited[] = $root; $root = $root->right; continue; } if (!in_array($root->value, $postOrder)) { $inorder[] = $root->value; } $root = $root->right; } return $postOrder; } } ``` ### BFS traversal ```php class TreeNode { public $data = NULL; public $children = []; public function __construct(string $data = NULL) { $this->data = $data; } /** * traverse tree and return path */ public function BFSTree(TreeNode $node): SplQueue { $queue = new SplQueue; $visited = new SplQueue; $queue->enqueue($node); while (!$queue->isEmpty()) { $current = $queue->dequeue(); $visited->enqueue($current); foreach ($current->children as $child) { $queue->enqueue($child); } } return $visited; } public function BFSGraph(array &$graph, int $start, array $visited): SplQueue { $queue = new SplQueue; $path = new SplQueue; $queue->enqueue($start); $visited[$start] = 1; while (!$queue->isEmpty()) { $node = $queue->dequeue(); $path->enqueue($node); foreach ($graph[$node] as $key => $vertex) { if (!$visited[$key] && $vertex == 1) { $visited[$key] = 1; $queue->enqueue($key); } } } return $path; } public function bfsStoringPerLevel($root) { $result, $queue = []; if(empty($root)){return [];} array_push($queue,$root); while(!empty($queue)){ $count = count($queue); $leveQueue = []; for($i=0;$i<$count;$i++){ $node = array_shift($queue); array_push($leveQueue,$node->val); if($node->left) array_push($queue,$node->left); if($node->right) array_push($queue,$node->right); } array_push($result,$leveQueue); } return $result; } } ```  ## DFS ```php /** There are **N** students in a class. Some of them are friends, while some are not. Their friendship is transitive in nature. For example, if A is a **direct** friend of B, and B is a **direct** friend of C, then A is an **indirect** friend of C. And we defined a friend circle is a group of students who are direct or indirect friends. Given a **N*N** matrix **M** representing the friend relationship between students in the class. If M[i][j] = 1, then the ith and jth students are **direct**friends with each other, otherwise not. And you have to output the total number of friend circles among all the students. */ class Solution { function visitFriends(&$M, &$visited, $m, $n) { if($m<0 || $m > count($M) || $n<0 || $n> count($M)) { return ; } $visited[$m][$n] = 1; $visited[$n][$m] = 1; for ($i = 0; $i < count($M[0]); $i++) { if ($M[$n][$i] == 1 && $visited[$n][$i]==0) { $this->visitFriends($M, $visited, $n, $i); } } } /** * @param Integer[][] $M * @return Integer */ function findCircleNum($M) { $visited = []; foreach ($M as $key1 => $item1) { foreach ($item1 as $key2 => $item2) { $visited[$key1][$key2] = 0; } } $count = 0; for ($i = 0; $i < count($M); $i++) { for ($j = 0; $j < count($M[0]); $j++) { if ($visited[$i][$j]===0 && $M[$i][$j] == 1) { $this->visitFriends($M, $visited, $i, $j); $count++; } } } return $count; } } /** Given a 2d grid map of `'1'`s (land) and `'0'`s (water), count the number of islands. An island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically. You may assume all four edges of the grid are all surrounded by water. **Example 1:** **Input:** 11110 11010 11000 00000 **Output:** 1 */ class Solution { /** * @param String[][] $grid * @return Integer */ function numIslands($grid) { $islands = 0; foreach ($grid as $i => $row) { foreach ($row as $j => $column) { if ($grid[$i][$j] == '1') { $islands++; $this->dfs($grid, $i, $j); } } } return $islands; } public function dfs(&$grid, $i, $j) { if ($i < 0 || $i >= count($grid) || $j < 0 || $j >= count($grid[0])) { return; } if ( isset($grid[$i]) && isset($grid[$i][$j]) && $grid[$i][$j] !== '1') { return; } $grid[$i][$j] = '*'; $this->dfs($grid, $i+1, $j); $this->dfs($grid, $i-1, $j); $this->dfs($grid, $i, $j+1); $this->dfs($grid, $i, $j-1); } } /** Given a binary tree, determine if it is a valid binary search tree (BST). Assume a BST is defined as follows: - The left subtree of a node contains only nodes with keys **less than** the node's key. - The right subtree of a node contains only nodes with keys **greater than** the node's key. - Both the left and right subtrees must also be binary search trees. */ class Solution { /** * @param TreeNode $root * @return Boolean */ function isValidBST($root) { $stack = new SplStack(); $inorder = PHP_INT_MIN; while (!$stack->isEmpty() || $root != null) { while ($root != null) { $stack->push($root); $root = $root->left; } $root = $stack->pop(); // If next element in inorder traversal is smaller than the previous one // that's not BST. if ($root->val <= $inorder) { return false; } $inorder = $root->val; $root = $root->right; } return true; } } ``` ## Sliding Window ```php /** Given a string S and a string T, find the minimum window in S which will contain all the characters in T in complexity O(n). **Example:** **Input: S** = "ADOBECODEBANC", **T** = "ABC" **Output:** "BANC" */ class Solution { public function minWindow(string $string1, string $string2) { $string1 = str_split($string1); $string2 = str_split($string2); if (count($string2)>count($string1)) { return ''; } if ($string1 === $string2) { return implode($string1); } $frequencyArray = $this->getFrequencyArray($string2); $begin = 0; $end = 0; $len = PHP_INT_MAX; $counter = count($frequencyArray); $result = []; // var_dump($frequencyArray);die; while ($end < count($string1)) { $endChar = $string1[$end]; // if current char found in table, decrement count if (array_key_exists($endChar, $frequencyArray)) { $frequencyArray[$endChar]--; if ($frequencyArray[$endChar] === 0) { $counter--; } } $end++; // if counter == 0, means we found an answer, now try to trim that window by // sliding begin to right. while ($counter === 0) { // store new answer if smaller than previously best if ( $end - $begin < $len) { $len = $end - $begin; $result = array_slice($string1, $begin, $end - $begin); } $startChar = $string1[$begin]; // startChar could be in frequencyArray, if not then it was a wasteful char and we shortened the prev substring. // if found in frequencyArray increment count in table, as we are leaving it out of window and moving ahead, // so it would no longer be a part of the substring marked by begin-end window // frequencyArray only has count of chars required to make the present //substring a valid candidate // if the count goes above zero means that the current window is missing one char // to be an answer candidate if ($this->countNumberOfElements($frequencyArray, $startChar) == 1) { $frequencyArray[$startChar]++; if ($frequencyArray[$startChar] > 0) { $counter++; } } $begin++; } } return implode('', $result); } public function getFrequencyArray($string2) { $frequencyArray = []; foreach ($string2 as $item) { if (isset($frequencyArray[$item])) { $frequencyArray[$item]++; } else { $frequencyArray[$item] = 1; } } return $frequencyArray; } public function countNumberOfElements($frequencyArray, $startChar) { $count = 0; foreach ($frequencyArray as $key => $item) { if ($startChar == $key) { $count++; } } return $count; } } /** Given a string, find the length of the **longest substring** without repeating characters.*/ class lengthOfLongestSubstringClass { /** * @param String $s * @return Integer */ function lengthOfLongestSubstring($s) { if ($s=="") { return 0;} $s = str_split($s); $n = count($s); $set = []; $ans = 0; $i = 0; $j = 0; while ($i < $n && $j < $n) { if (!in_array($s[$j], $set)){ $set[$s[$j]] = $s[$j]; $j++; $ans = max($ans,$j-$i); } else { unset($set[$s[$i]]); $i++; } } return $ans; } } /** Given two strings **s1** and **s2**, write a function to return true if **s2** contains the permutation of **s1**. In other words, one of the first string's permutations is the **substring** of the second string. **Example 1:** **Input:** s1 = "ab" s2 = "eidbaooo" **Output:** True **Explanation:** s2 contains one permutation of s1 ("ba"). */ class Solution { function checkInclusion($s1, $s2) { $string1 = str_split($s2); $string2 = str_split($s1); $frequencyArray = []; foreach ($string2 as $item) { if (isset($frequencyArray[$item])) { $frequencyArray[$item]++; } else { $frequencyArray[$item] = 1; } } $counter = count($frequencyArray); $end = 0; $begin = 0; while ($end < count($string1)) { $endChar = $string1[$end]; if (array_key_exists($endChar, $frequencyArray)) { $frequencyArray[$endChar]--; if ($frequencyArray[$endChar]==0) { $counter--; } } $end++; while ($counter == 0) { $beginChar = $string1[$begin]; if (array_key_exists($beginChar, $frequencyArray)) { $frequencyArray[$beginChar]++; if ($frequencyArray[$beginChar] > 0) { $counter++; } } if ($end - $begin == count($string2)) { return true; } $begin++; } } return false; } } ``` ## BackTracking Backtracking is an algorithm for finding all solutions by exploring all potential candidates. If the solution candidate turns to be _not_ a solution (or at least not the _last_ one), backtracking algorithm discards it by making some changes on the previous step, ```php class subsetsClass { private $powerset = []; private $subset = []; public function subsets(array &$nums): array { $this->backTrack($nums, 0); return $this->powerset; } public function backTrack(array &$nums, int $start): void { $this->powerset[] = $this->subset; $size = count($nums); for ($i = $start; $i < $size; $i++) { $this->subset[] = $nums[$i]; $this->backTrack($nums, $i+1); array_pop($this->subset); } } } /** ***Input:** candidates = [2,3,5]`,` target = 8, **A solution set is:** * [ * [2,2,2,2], * [2,3,3], * [3,5] * ] */ class combinationSumClass { private $result, $subset = []; private $target; function combinationSum($candidates, $target) { $this->target = $target; $this->combinationSumRec($candidates); return $this->result; } public function combinationSumRec(array &$candidates): void { if (array_sum($this->subset) <= $this->target) { if (array_sum($this->subset) === $this->target) { sort($this->subset); if (!in_array($this->subset, $this->result)) { $this->result[] = $this->subset; } } $size = count($candidates); for ($i = 0; $i < $size; $i++) { $this->subset[] = $candidates[$i]; $this->combinationSumRec($candidates); array_pop($this->subset); } } } } // Given a collection of **distinct** integers, return all possible permutations. /** */ class Solution { /** * @param Integer[] $nums * @return Integer[][] */ function permute($nums) { $result = array(); $this->backTracking($nums, count($nums), 0, array(), $result); return $result; } function backTracking($nums, $numsLength, $startIndex, $permutation, &$result) { if (count($permutation) == $numsLength) { array_push($result, $permutation); return; } for($i = $startIndex; $i < $numsLength; $i++) { if (!in_array($nums[$i], $permutation)) { array_push($permutation, $nums[$i]); $this->backTracking($nums, $numsLength, 0, $permutation, $result); array_pop($permutation); } } } } class gardenNoAdjClass3 { public $paths; public $numberOfGardens; public function gardenNoAdj($numberOfGardens, $paths) { $this->paths = $paths; $this->numberOfGardens = $numberOfGardens; $solution = array_fill(1, $numberOfGardens, null); $this->solve($solution, 1); return $solution; } public function solve(&$solution, $position) { if ($position > count($solution)) { return true; } for($i = 1; $i <= 4; $i++) { $solution[$position] = $i; if ($this->correctUntilHere($solution)) { if ($this->solve($solution, $position+1)) { return true; } } $solution[$position] = null; } } public function correctUntilHere($solution) { foreach ($this->paths as $path) { if ($solution[$path[0]] == $solution[$path[1]] && $solution[$path[0]]!==null) { return false; } } return true; } } ``` ## Dynamic Programming ```php /** Given a string **s**, find the longest palindromic substring in **s**. You may assume that the maximum length of **s** is 1000. **Example 1:** **Input:** "babad" **Output:** "bab" **Note:** "aba" is also a valid answer. */ class Solution { /** * @param String $s * @return String */ function longestPalindrome($s) { $a = str_split($s); $maxLength = 0; $maxArray = []; for ($i = 0; $i < count($a); $i++){ for ($j = 1; $j < count($a); $j++) { if (isset($a[$i-$j])) { $bottom = $a[$i-$j]; } else { break; } if (isset($a[$i+$j])) { $top = $a[$i+$j]; } else { break; } if ($bottom == $top) { $length = $j+1; if ($length > $maxLength) { $maxLength = $length; $maxArray = array_slice($a,$i-$j, $length+$j); } } else { break; } } } return implode($maxArray); } } /** Say you have an array for which the _i_th element is the price of a given stock on day _i_. If you were only permitted to complete at most one transaction (i.e., buy one and sell one share of the stock), design an algorithm to find the maximum profit. Note that you cannot sell a stock before you buy one. **Example 1:** **Input:** [7,1,5,3,6,4] **Output:** 5 */ class Solution { /** * @param Integer[] $prices * @return Integer */ function maxProfit($prices) { $minValue = max($prices); $maxProfit = 0; for($i=0;$i $maxProfit){ $maxProfit = $prices[$i]-$minValue; } } return $maxProfit; } } /** Given an integer array `nums`, find the contiguous subarray (containing at least one number) which has the largest sum and return its sum. **Example:** **Input:** [-2,1,-3,4,-1,2,1,-5,4], **Output:** 6 **Explanation:** [4,-1,2,1] has the largest sum = 6. */ class Solution { /** * @param Integer[] $nums * @return Integer */ function maxSubArray($nums) { $cur=$nums[0]; $res=$nums[0]; for($i=1;$i