8000 Added tasks 101-136 · pytdev/LeetCode-in-Php@e1d334e · GitHub
[go: up one dir, main page]
Skip to content

Commit e1d334e

Browse files
javadevjavadev
authored
Added tasks 101-136
1 parent 571354a commit e1d334e

File tree

33 files changed

+984
-3
lines changed

33 files changed

+984
-3
lines changed

‎README.md

Lines changed: 30 additions & 2 deletions
Large diffs are not rendered by default.

‎src/main/php/com_github_leetcode/TreeNode.php

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -7,7 +7,7 @@ class TreeNode {
77
public $left;
88
public $right;
99

10-
function __construct($val, $left = null, $right = null) {
10+
function __construct($val = 0, $left = null, $right = null) {
1111
$this->val = $val;
1212
$this->left = $left;
1313
$this->right = $right;

‎src/main/php/g0101_0200/s0101_symmetric_tree/Solution.php

Lines changed: 43 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,43 @@
1+
<?php
2+
3+
namespace leetcode\g0101_0200\s0101_symmetric_tree;
4+
5+
// #Easy #Top_100_Liked_Questions #Top_Interview_Questions #Depth_First_Search #Breadth_First_Search
6+
// #Tree #Binary_Tree #Data_Structure_I_Day_11_Tree #Level_2_Day_15_Tree
7+
// #Big_O_Time_O(N)_Space_O(log(N)) #2023_12_11_Time_6_ms_(76.40%)_Space_19.4_MB_(28.09%)
8+
9+
/**
10+
* Definition for a binary tree node.
11+
* class TreeNode {
12+
* public $val = null;
13+
* public $left = null;
14+
* public $right = null;
15+
* function __construct($val = 0, $left = null, $right = null) {
16+
* $this->val = $val;
17+
* $this->left = $left;
18+
* $this->right = $right;
19+
* }
20+
* }
21+
*/
22+
class Solution {
23+
/**
24+
* @param TreeNode $root
25+
* @return Boolean
26+
*/
27+
function isSymmetric($root) {
28+
if ($root == null) {
29+
return true;
30+
}
31+
return $this->helper($root->left, $root->right);
32+
}
33+
34+
private function helper($leftNode, $rightNode) {
35+
if ($leftNode == null || $rightNode == null) {
36+
return $leftNode == null && $rightNode == null;
37+
}
38+
if ($leftNode->val != $rightNode->val) {
39+
return false;
40+
}
41+
return $this->helper($leftNode->left, $rightNode->right) && $this->helper($leftNode->right, $rightNode->left);
42+
}
43+
}

‎src/main/php/g0101_0200/s0101_symmetric_tree/readme.md

Lines changed: 28 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,28 @@
1+
101\. Symmetric Tree
2+
3+
Easy
4+
5+
Given the `root` of a binary tree, _check whether it is a mirror of itself_ (i.e., symmetric around its center).
6+
7+
**Example 1:**
8+
9+
![](https://assets.leetcode.com/uploads/2021/02/19/symtree1.jpg)
10+
11+
**Input:** root = [1,2,2,3,4,4,3]
12+
13+
**Output:** true
14+
15+
**Example 2:**
16+
17+
![](https://assets.leetcode.com/uploads/2021/02/19/symtree2.jpg)
18+
19+
**Input:** root = [1,2,2,null,3,null,3]
20+
21+
**Output:** false
22+
23+
**Constraints:**
24+
25+
* The number of nodes in the tree is in the range `[1, 1000]`.
26+
* `-100 <= Node.val <= 100`
27+
28+
**Follow up:** Could you solve it both recursively and iteratively?

‎src/main/php/g0101_0200/s0102_binary_tree_level_order_traversal/Solution.php

Lines changed: 56 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,56 @@
1+
<?php
2+
3+
namespace leetcode\g0101_0200\s0102_binary_tree_level_order_traversal;
4+
5+
// #Medium #Top_100_Liked_Questions #Top_Interview_Questions #Breadth_First_Search #Tree
6+
// #Binary_Tree #Data_Structure_I_Day_11_Tree #Level_1_Day_6_Tree #Udemy_Tree_Stack_Queue
7+
// #Big_O_Time_O(N)_Space_O(N) #2023_12_11_Time_4_ms_(96.08%)_Space_20.9_MB_(50.98%)
8+
9+
/**
10+
* Definition for a binary tree node.
11+
* class TreeNode {
12+
* public $val = null;
13+
* public $left = null;
14+
* public $right = null;
15+
* function __construct($val = 0, $left = null, $right = null) {
16+
* $this->val = $val;
17+
* $this->left = $left;
18+
* $this->right = $right;
19+
* }
20+
* }
21+
*/
22+
class Solution {
23+
/**
24+
* @param TreeNode $root
25+
* @return Integer[][]
26+
*/
27+
function levelOrder($root) {
28+
$result = array();
29+
if ($root == null) {
30+
return $result;
31+
}
32+
$queue = new \SplQueue();
33+
$queue->enqueue($root);
34+
$queue->enqueue(null);
35+
$level = array();
36+
while (!$queue->isEmpty()) {
37+
$root = $queue->dequeue();
38+
while (!$queue->isEmpty() && $root != null) {
39+
array_push($level, $root->val);
40+
if ($root->left != null) {
41+
$queue->enqueue($root->left);
42+
}
43+
if ($root->right != null) {
44+
$queue->enqueue($root->right);
45+
}
46+
$root = $queue->dequeue();
47+
}
48+
array_push($result, $level);
49+
$level = array();
50+
if (!$queue->isEmpty()) {
51+
$queue->enqueue(null);
52+
}
53+
}
54+
return $result;
55+
}
56+
}

‎src/main/php/g0101_0200/s0102_binary_tree_level_order_traversal/readme.md

Lines changed: 30 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,30 @@
1+
102\. Binary Tree Level Order Traversal
2+
3+
Medium
4+
5+
Given the `root` of a binary tree, return _the level order traversal of its nodes' values_. (i.e., from left to right, level by level).
6+
7+
**Example 1:**
8+
9+
![](https://assets.leetcode.com/uploads/2021/02/19/tree1.jpg)
10+
11+
**Input:** root = [3,9,20,null,null,15,7]
12+
13+
**Output:** [[3],[9,20],[15,7]]
14+
15+
**Example 2:**
16+
17+
**Input:** root = [1]
18+
19+
**Output:** [[1]]
20+
21+
**Example 3:**
22+
23+
**Input:** root = []
24+
25+
**Output:** []
26+
27+
**Constraints:**
28+
29+
* The number of nodes in the tree is in the range `[0, 2000]`.
30+
* `-1000 <= Node.val <= 1000`

‎src/main/php/g0101_0200/s0104_maximum_depth_of_binary_tree/Solution.php

Lines changed: 40 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,40 @@
1+
<?php
2+
3+
namespace leetcode\g0101_0200\s0104_maximum_depth_of_binary_tree;
4+
5+
// #Easy #Top_100_Liked_Questions #Top_Interview_Questions #Depth_First_Search #Breadth_First_Search
6+
// #Tree #Binary_Tree #Data_Structure_I_Day_11_Tree
7+
// #Programming_Skills_I_Day_10_Linked_List_and_Tree #Udemy_Tree_Stack_Queue
8+
// #Big_O_Time_O(N)_Space_O(H) #2023_12_11_Time_9_ms_(63.06%)_Space_20.5_MB_(87.90%)
9+
10+
/**
11+
* Definition for a binary tree node.
12+
* class TreeNode {
13+
* public $val = null;
14+
* public $left = null;
15+
* public $right = null;
16+
* function __construct($val = 0, $left = null, $right = null) {
17+
* $this->val = $val;
18+
* $this->left = $left;
19+
* $this->right = $right;
20+
* }
21+
* }
22+
*/
23+
class Solution {
24+
/**
25+
* @param TreeNode $root
26+
* @return Integer
27+
*/
28+
function maxDepth($root) {
29+
return $this->findDepth($root, 0);
30+
}
31+
32+
private function findDepth($node, $currentDepth) {
33+
if ($node == null) {
34+
return 0;
35+
}
36+
$currentDepth++;
37+
return 1
38+
+ max($this->findDepth($node->left, $currentDepth), $this->findDepth($node->right, $currentDepth));
39+
}
40+
}

‎src/main/php/g0101_0200/s0104_maximum_depth_of_binary_tree/readme.md

Lines changed: 38 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,38 @@
1+
104\. Maximum Depth of Binary Tree
2+
3+
Easy
4+
5+
Given the `root` of a binary tree, return _its maximum depth_.
6+
7+
A binary tree's **maximum depth** is the number of nodes along the longest path from the root node down to the farthest leaf node.
8+
9+
**Example 1:**
10+
11+
![](https://assets.leetcode.com/uploads/2020/11/26/tmp-tree.jpg)
12+
13+
**Input:** root = [3,9,20,null,null,15,7]
14+
15+
**Output:** 3
16+
17+
**Example 2:**
18+
19+
**Input:** root = [1,null,2]
20+
21+
**Output:** 2
22+
23+
**Example 3:**
24+
25+
**Input:** root = []
26+
27+
**Output:** 0
28+
29+
**Example 4:**
30+
31+
**Input:** root = [0]
32+
33+
**Output:** 1
34+
35+
**Constraints:**
36+
37+
* The number of nodes in the tree is in the range <code>[0, 10<sup>4</sup>]</code>.
38+
* `-100 <= Node.val <= 100`

‎src/main/php/g0101_0200/s0105_construct_binary_tree_from_preorder_and_inorder_traversal/Solution.php

Lines changed: 61 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,61 @@
1+
<?php
2+
3+
namespace leetcode\g0101_0200\s0105_construct_binary_tree_from_preorder_and_inorder_traversal;
4+
5+
// #Medium #Top_100_Liked_Questions #Top_Interview_Questions #Array #Hash_Table #Tree #Binary_Tree
6+
// #Divide_and_Conquer #Data_Structure_II_Day_15_Tree #Big_O_Time_O(N)_Space_O(N)
7+
// #2023_12_11_Time_14_ms_(63.33%)_Space_21.1_MB_(93.33%)
8+
9+
use leetcode\com_github_leetcode\TreeNode;
10+
11+
/**
12+
* Definition for a binary tree node.
13+
* class TreeNode {
14+
* public $val = null;
15+
* public $left = null;
16+
* public $right = null;
17+
* function __construct($val = 0, $left = null, $right = null) {
18+
* $this->val = $val;
19+
* $this->left = $left;
20+
* $this->right = $right;
21+
* }
22+
* }
23+
*/
24+
class Solution {
25+
private $j;
26+
private $map;
27+
28+
function __construct() {
29+
$this->j = 0;
30+
$this->map = array();
31+
}
32+
33+
function get($key) {
34+
return $this->map[$key];
35+
}
36+
37+
private function answer($preorder, $inorder, $start, $end) {
38+
if ($start > $end || $this->j > count($preorder)) {
39+
return null;
40+
}
41+
$value = $preorder[$this->j++];
42+
$index = $this->get($value);
43+
$node = new TreeNode($value);
44+
$node->left = $this->answer($preorder, $inorder, $start, $index - 1);
45+
$node->right = $this->answer($preorder, $inorder, $index + 1, $end);
46+
return $node;
47+
}
48+
49+
/**
50+
* @param Integer[] $preorder
51+
* @param Integer[] $inorder
52+
* @return TreeNode
53+
*/
54+
function buildTree($preorder, $inorder) {
55+
$this->j = 0;
56+
for ($i = 0; $i < count($preorder); $i++) {
57+
$this->map[$inorder[$i]] = $i;
58+
}
59+
return $this->answer($preorder, $inorder, 0, count($preorder) - 1);
60+
}
61+
}

‎src/main/php/g0101_0200/s0105_construct_binary_tree_from_preorder_and_inorder_traversal/readme.md

Lines changed: 29 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,29 @@
1+
105\. Construct Binary Tree from Preorder and Inorder Traversal
2+
3+
Medium
4+
5+
Given two integer arrays `preorder` and `inorder` where `preorder` is the preorder traversal of a binary tree and `inorder` is the inorder traversal of the same tree, construct and return _the binary tree_.
6+
7+
**Example 1:**
8+
9+
![](https://assets.leetcode.com/uploads/2021/02/19/tree.jpg)
10+
11+
**Input:** preorder = [3,9,20,15,7], inorder = [9,3,15,20,7]
12+
13+
**Output:** [3,9,20,null,null,15,7]
14+
15+
**Example 2:**
16+
17+
**Input:** preorder = [-1], inorder = [-1]
18+
19+
**Output:** [-1]
20+
21+
**Constraints:**
22+
23+
* `1 <= preorder.length <= 3000`
24+
* `inorder.length == preorder.length`
25+
* `-3000 <= preorder[i], inorder[i] <= 3000`
26+
* `preorder` and `inorder` consist of **unique** values.
27+
* Each value of `inorder` also appears in `preorder`.
28+
* `preorder` is **guaranteed** to be the preorder traversal of the tree.
29+
* `inorder` is **guaranteed** to be the inorder traversal of the tree.

0 commit comments

Comments
 (0)
0