Given a tree, find a downward path with the maximal number of direction changes.
Your browser (Unknown 0) is no longer supported. Some parts of the website may not work correctly. Please update your browser.
AVAILABLE EXERCISES:
Exercise 9
Bitwise operations (bit-ops)
Exercise 8
Frontend
Exercise 7
Data Structures
Exercise 6
SQL
Exercise 5
Coding skills
Exercise 4
Algorithmic skills
Exercise 3
2017 Contest
Exercise 2
2016 Contest
Exercise 1
2015 Contest
Spoken language:
In this problem we consider binary trees. Let's define a turn on a path as a change in the direction of the path (i.e. a switch from right to left or vice versa). A zigzag is simply a sequence of turns (it can start with either right or left). The length of a zigzag is equal to the number of turns.
Consider binary tree below:
There are two turns on the marked path. The first one is at [15]; the second is at [30]. That means that the length of this zigzag is equal to 2. This is also the longest zigzag in the tree under consideration. In this problem you should find the longest zigzag that starts at the root of any given binary tree and form a downwards path.
Note that a zigzag containing only one edge or one node has length 0.
Problem
Write a function:
int solution(struct tree * T);
that, given a non-empty binary tree T consisting of N nodes, returns the length of the longest zigzag starting at the root.
For example, given tree T shown in the figure above, the function should return 2, as explained above. Note that the values contained in the nodes are not relevant in this task.
Technical details
A binary tree can be specified using a pointer data structure. Assume that the following declarations are given:
struct tree { int x; struct tree * l; struct tree * r; };
An empty tree is represented by an empty pointer (denoted by NULL). A non-empty tree is represented by a pointer to an object representing its root. The attribute x holds the integer contained in the root, whereas attributes l and r hold the left and right subtrees of the binary tree, respectively.
For the purpose of entering your own test cases, you can denote a tree recursively in the following way. An empty binary tree is denoted by None. A non-empty tree is denoted as (X, L, R), where X is the value contained in the root and L and R denote the left and right subtrees, respectively. The tree from the above figure can be denoted as:
(5, (3, (20, (6, None, None), None), None), (10, (1, None, None), (15, (30, None, (9, None, None)), (8, None, None))))Assumptions
Write an efficient algorithm for the following assumptions:
- N is an integer within the range [1..100,000];
- the height of tree T (number of edges on the longest path from root to leaf) is within the range [0..800].
Copyright 2009–2025 by Codility Limited. All Rights Reserved. Unauthorized copying, publication or disclosure prohibited.
In this problem we consider binary trees. Let's define a turn on a path as a change in the direction of the path (i.e. a switch from right to left or vice versa). A zigzag is simply a sequence of turns (it can start with either right or left). The length of a zigzag is equal to the number of turns.
Consider binary tree below:
There are two turns on the marked path. The first one is at [15]; the second is at [30]. That means that the length of this zigzag is equal to 2. This is also the longest zigzag in the tree under consideration. In this problem you should find the longest zigzag that starts at the root of any given binary tree and form a downwards path.
Note that a zigzag containing only one edge or one node has length 0.
Problem
Write a function:
int solution(tree * T);
that, given a non-empty binary tree T consisting of N nodes, returns the length of the longest zigzag starting at the root.
For example, given tree T shown in the figure above, the function should return 2, as explained above. Note that the values contained in the nodes are not relevant in this task.
Technical details
A binary tree can be specified using a pointer data structure. Assume that the following declarations are given:
struct tree { int x; tree * l; tree * r; };
An empty tree is represented by an empty pointer (denoted by nullptr). A non-empty tree is represented by a pointer to an object representing its root. The attribute x holds the integer contained in the root, whereas attributes l and r hold the left and right subtrees of the binary tree, respectively.
For the purpose of entering your own test cases, you can denote a tree recursively in the following way. An empty binary tree is denoted by None. A non-empty tree is denoted as (X, L, R), where X is the value contained in the root and L and R denote the left and right subtrees, respectively. The tree from the above figure can be denoted as:
(5, (3, (20, (6, None, None), None), None), (10, (1, None, None), (15, (30, None, (9, None, None)), (8, None, None))))Assumptions
Write an efficient algorithm for the following assumptions:
- N is an integer within the range [1..100,000];
- the height of tree T (number of edges on the longest path from root to leaf) is within the range [0..800].
Copyright 2009–2025 by Codility Limited. All Rights Reserved. Unauthorized copying, publication or disclosure prohibited.
In this problem we consider binary trees. Let's define a turn on a path as a change in the direction of the path (i.e. a switch from right to left or vice versa). A zigzag is simply a sequence of turns (it can start with either right or left). The length of a zigzag is equal to the number of turns.
Consider binary tree below:
There are two turns on the marked path. The first one is at [15]; the second is at [30]. That means that the length of this zigzag is equal to 2. This is also the longest zigzag in the tree under consideration. In this problem you should find the longest zigzag that starts at the root of any given binary tree and form a downwards path.
Note that a zigzag containing only one edge or one node has length 0.
Problem
Write a function:
class Solution { public int solution(Tree T); }
that, given a non-empty binary tree T consisting of N nodes, returns the length of the longest zigzag starting at the root.
For example, given tree T shown in the figure above, the function should return 2, as explained above. Note that the values contained in the nodes are not relevant in this task.
Technical details
A binary tree can be specified using a pointer data structure. Assume that the following declarations are given:
class Tree { public int x; public Tree l; public Tree r; };
An empty tree is represented by an empty pointer (denoted by null). A non-empty tree is represented by a pointer to an object representing its root. The attribute x holds the integer contained in the root, whereas attributes l and r hold the left and right subtrees of the binary tree, respectively.
For the purpose of entering your own test cases, you can denote a tree recursively in the following way. An empty binary tree is denoted by None. A non-empty tree is denoted as (X, L, R), where X is the value contained in the root and L and R denote the left and right subtrees, respectively. The tree from the above figure can be denoted as:
(5, (3, (20, (6, None, None), None), None), (10, (1, None, None), (15, (30, None, (9, None, None)), (8, None, None))))Assumptions
Write an efficient algorithm for the following assumptions:
- N is an integer within the range [1..100,000];
- the height of tree T (number of edges on the longest path from root to leaf) is within the range [0..800].
Copyright 2009–2025 by Codility Limited. All Rights Reserved. Unauthorized copying, publication or disclosure prohibited.
In this problem we consider binary trees. Let's define a turn on a path as a change in the direction of the path (i.e. a switch from right to left or vice versa). A zigzag is simply a sequence of turns (it can start with either right or left). The length of a zigzag is equal to the number of turns.
Consider binary tree below:
There are two turns on the marked path. The first one is at [15]; the second is at [30]. That means that the length of this zigzag is equal to 2. This is also the longest zigzag in the tree under consideration. In this problem you should find the longest zigzag that starts at the root of any given binary tree and form a downwards path.
Note that a zigzag containing only one edge or one node has length 0.
Problem
Write a function:
int solution(Tree? T);
that, given a non-empty binary tree T consisting of N nodes, returns the length of the longest zigzag starting at the root.
For example, given tree T shown in the figure above, the function should return 2, as explained above. Note that the values contained in the nodes are not relevant in this task.
Technical details
A binary tree can be specified using a pointer data structure. Assume that the following declarations are given:
class Tree { int x = 0; Tree? l = null; Tree? r = null; }
An empty tree is represented by an empty pointer (denoted by null). A non-empty tree is represented by a pointer to an object representing its root. The attribute x holds the integer contained in the root, whereas attributes l and r hold the left and right subtrees of the binary tree, respectively.
For the purpose of entering your own test cases, you can denote a tree recursively in the following way. An empty binary tree is denoted by None. A non-empty tree is denoted as (X, L, R), where X is the value contained in the root and L and R denote the left and right subtrees, respectively. The tree from the above figure can be denoted as:
(5, (3, (20, (6, None, None), None), None), (10, (1, None, None), (15, (30, None, (9, None, None)), (8, None, None))))Assumptions
Write an efficient algorithm for the following assumptions:
- N is an integer within the range [1..100,000];
- the height of tree T (number of edges on the longest path from root to leaf) is within the range [0..800].
Copyright 2009–2025 by Codility Limited. All Rights Reserved. Unauthorized copying, publication or disclosure prohibited.
In this problem we consider binary trees. Let's define a turn on a path as a change in the direction of the path (i.e. a switch from right to left or vice versa). A zigzag is simply a sequence of turns (it can start with either right or left). The length of a zigzag is equal to the number of turns.
Consider binary tree below:
There are two turns on the marked path. The first one is at [15]; the second is at [30]. That means that the length of this zigzag is equal to 2. This is also the longest zigzag in the tree under consideration. In this problem you should find the longest zigzag that starts at the root of any given binary tree and form a downwards path.
Note that a zigzag containing only one edge or one node has length 0.
Problem
Write a function:
func Solution(T *Tree) int
that, given a non-empty binary tree T consisting of N nodes, returns the length of the longest zigzag starting at the root.
For example, given tree T shown in the figure above, the function should return 2, as explained above. Note that the values contained in the nodes are not relevant in this task.
Technical details
A binary tree can be specified using a pointer data structure. Assume that the following declarations are given:
type Tree struct { X int L *Tree R *Tree }
An empty tree is represented by an empty pointer (denoted by nil). A non-empty tree is represented by a pointer to an object representing its root. The attribute x holds the integer contained in the root, whereas attributes l and r hold the left and right subtrees of the binary tree, respectively.
For the purpose of entering your own test cases, you can denote a tree recursively in the following way. An empty binary tree is denoted by None. A non-empty tree is denoted as (X, L, R), where X is the value contained in the root and L and R denote the left and right subtrees, respectively. The tree from the above figure can be denoted as:
(5, (3, (20, (6, None, None), None), None), (10, (1, None, None), (15, (30, None, (9, None, None)), (8, None, None))))Assumptions
Write an efficient algorithm for the following assumptions:
- N is an integer within the range [1..100,000];
- the height of tree T (number of edges on the longest path from root to leaf) is within the range [0..800].
Copyright 2009–2025 by Codility Limited. All Rights Reserved. Unauthorized copying, publication or disclosure prohibited.
In this problem we consider binary trees. Let's define a turn on a path as a change in the direction of the path (i.e. a switch from right to left or vice versa). A zigzag is simply a sequence of turns (it can start with either right or left). The length of a zigzag is equal to the number of turns.
Consider binary tree below:
There are two turns on the marked path. The first one is at [15]; the second is at [30]. That means that the length of this zigzag is equal to 2. This is also the longest zigzag in the tree under consideration. In this problem you should find the longest zigzag that starts at the root of any given binary tree and form a downwards path.
Note that a zigzag containing only one edge or one node has length 0.
Problem
Write a function:
class Solution { public int solution(Tree T); }
that, given a non-empty binary tree T consisting of N nodes, returns the length of the longest zigzag starting at the root.
For example, given tree T shown in the figure above, the function should return 2, as explained above. Note that the values contained in the nodes are not relevant in this task.
Technical details
A binary tree can be specified using a pointer data structure. Assume that the following declarations are given:
class Tree { public int x; public Tree l; public Tree r; }
An empty tree is represented by an empty pointer (denoted by null). A non-empty tree is represented by a pointer to an object representing its root. The attribute x holds the integer contained in the root, whereas attributes l and r hold the left and right subtrees of the binary tree, respectively.
For the purpose of entering your own test cases, you can denote a tree recursively in the following way. An empty binary tree is denoted by None. A non-empty tree is denoted as (X, L, R), where X is the value contained in the root and L and R denote the left and right subtrees, respectively. The tree from the above figure can be denoted as:
(5, (3, (20, (6, None, None), None), None), (10, (1, None, None), (15, (30, None, (9, None, None)), (8, None, None))))Assumptions
Write an efficient algorithm for the following assumptions:
- N is an integer within the range [1..100,000];
- the height of tree T (number of edges on the longest path from root to leaf) is within the range [0..800].
Copyright 2009–2025 by Codility Limited. All Rights Reserved. Unauthorized copying, publication or disclosure prohibited.
In this problem we consider binary trees. Let's define a turn on a path as a change in the direction of the path (i.e. a switch from right to left or vice versa). A zigzag is simply a sequence of turns (it can start with either right or left). The length of a zigzag is equal to the number of turns.
Consider binary tree below:
There are two turns on the marked path. The first one is at [15]; the second is at [30]. That means that the length of this zigzag is equal to 2. This is also the longest zigzag in the tree under consideration. In this problem you should find the longest zigzag that starts at the root of any given binary tree and form a downwards path.
Note that a zigzag containing only one edge or one node has length 0.
Problem
Write a function:
class Solution { public int solution(Tree T); }
that, given a non-empty binary tree T consisting of N nodes, returns the length of the longest zigzag starting at the root.
For example, given tree T shown in the figure above, the function should return 2, as explained above. Note that the values contained in the nodes are not relevant in this task.
Technical details
A binary tree can be specified using a pointer data structure. Assume that the following declarations are given:
class Tree { public int x; public Tree l; public Tree r; }
An empty tree is represented by an empty pointer (denoted by null). A non-empty tree is represented by a pointer to an object representing its root. The attribute x holds the integer contained in the root, whereas attributes l and r hold the left and right subtrees of the binary tree, respectively.
For the purpose of entering your own test cases, you can denote a tree recursively in the following way. An empty binary tree is denoted by None. A non-empty tree is denoted as (X, L, R), where X is the value contained in the root and L and R denote the left and right subtrees, respectively. The tree from the above figure can be denoted as:
(5, (3, (20, (6, None, None), None), None), (10, (1, None, None), (15, (30, None, (9, None, None)), (8, None, None))))Assumptions
Write an efficient algorithm for the following assumptions:
- N is an integer within the range [1..100,000];
- the height of tree T (number of edges on the longest path from root to leaf) is within the range [0..800].
Copyright 2009–2025 by Codility Limited. All Rights Reserved. Unauthorized copying, publication or disclosure prohibited.
In this problem we consider binary trees. Let's define a turn on a path as a change in the direction of the path (i.e. a switch from right to left or vice versa). A zigzag is simply a sequence of turns (it can start with either right or left). The length of a zigzag is equal to the number of turns.
Consider binary tree below:
There are two turns on the marked path. The first one is at [15]; the second is at [30]. That means that the length of this zigzag is equal to 2. This is also the longest zigzag in the tree under consideration. In this problem you should find the longest zigzag that starts at the root of any given binary tree and form a downwards path.
Note that a zigzag containing only one edge or one node has length 0.
Problem
Write a function:
function solution(T);
that, given a non-empty binary tree T consisting of N nodes, returns the length of the longest zigzag starting at the root.
For example, given tree T shown in the figure above, the function should return 2, as explained above. Note that the values contained in the nodes are not relevant in this task.
Technical details
A binary tree can be specified using a pointer data structure. Assume that the following declarations are given:
// Tree obj is an Object with attributes // obj.x - type: int // obj.l - type: Tree // obj.r - type: Tree
An empty tree is represented by an empty pointer (denoted by null). A non-empty tree is represented by a pointer to an object representing its root. The attribute x holds the integer contained in the root, whereas attributes l and r hold the left and right subtrees of the binary tree, respectively.
For the purpose of entering your own test cases, you can denote a tree recursively in the following way. An empty binary tree is denoted by None. A non-empty tree is denoted as (X, L, R), where X is the value contained in the root and L and R denote the left and right subtrees, respectively. The tree from the above figure can be denoted as:
(5, (3, (20, (6, None, None), None), None), (10, (1, None, None), (15, (30, None, (9, None, None)), (8, None, None))))Assumptions
Write an efficient algorithm for the following assumptions:
- N is an integer within the range [1..100,000];
- the height of tree T (number of edges on the longest path from root to leaf) is within the range [0..800].
Copyright 2009–2025 by Codility Limited. All Rights Reserved. Unauthorized copying, publication or disclosure prohibited.
In this problem we consider binary trees. Let's define a turn on a path as a change in the direction of the path (i.e. a switch from right to left or vice versa). A zigzag is simply a sequence of turns (it can start with either right or left). The length of a zigzag is equal to the number of turns.
Consider binary tree below:
There are two turns on the marked path. The first one is at [15]; the second is at [30]. That means that the length of this zigzag is equal to 2. This is also the longest zigzag in the tree under consideration. In this problem you should find the longest zigzag that starts at the root of any given binary tree and form a downwards path.
Note that a zigzag containing only one edge or one node has length 0.
Problem
Write a function:
function solution(T)
that, given a non-empty binary tree T consisting of N nodes, returns the length of the longest zigzag starting at the root.
For example, given tree T shown in the figure above, the function should return 2, as explained above. Note that the values contained in the nodes are not relevant in this task.
Technical details
A binary tree can be specified using a pointer data structure. Assume that the following declarations are given:
-- Tree obj is an object with attributes -- obj.x - type: int -- obj.l - type: Tree -- obj.r - type: Tree
An empty tree is represented by an empty pointer (denoted by nil). A non-empty tree is represented by a pointer to an object representing its root. The attribute x holds the integer contained in the root, whereas attributes l and r hold the left and right subtrees of the binary tree, respectively.
For the purpose of entering your own test cases, you can denote a tree recursively in the following way. An empty binary tree is denoted by None. A non-empty tree is denoted as (X, L, R), where X is the value contained in the root and L and R denote the left and right subtrees, respectively. The tree from the above figure can be denoted as:
(5, (3, (20, (6, None, None), None), None), (10, (1, None, None), (15, (30, None, (9, None, None)), (8, None, None))))Assumptions
Write an efficient algorithm for the following assumptions:
- N is an integer within the range [1..100,000];
- the height of tree T (number of edges on the longest path from root to leaf) is within the range [0..800].
Copyright 2009–2025 by Codility Limited. All Rights Reserved. Unauthorized copying, publication or disclosure prohibited.
In this problem we consider binary trees. Let's define a turn on a path as a change in the direction of the path (i.e. a switch from right to left or vice versa). A zigzag is simply a sequence of turns (it can start with either right or left). The length of a zigzag is equal to the number of turns.
Consider binary tree below:
There are two turns on the marked path. The first one is at [15]; the second is at [30]. That means that the length of this zigzag is equal to 2. This is also the longest zigzag in the tree under consideration. In this problem you should find the longest zigzag that starts at the root of any given binary tree and form a downwards path.
Note that a zigzag containing only one edge or one node has length 0.
Problem
Write a function:
int solution(Tree * T);
that, given a non-empty binary tree T consisting of N nodes, returns the length of the longest zigzag starting at the root.
For example, given tree T shown in the figure above, the function should return 2, as explained above. Note that the values contained in the nodes are not relevant in this task.
Technical details
A binary tree can be specified using a pointer data structure. Assume that the following declarations are given:
@interface Tree : NSObject { @public int x; Tree * l; Tree * r; } @end @implementation Tree @end
An empty tree is represented by an empty pointer (denoted by nil). A non-empty tree is represented by a pointer to an object representing its root. The attribute x holds the integer contained in the root, whereas attributes l and r hold the left and right subtrees of the binary tree, respectively.
For the purpose of entering your own test cases, you can denote a tree recursively in the following way. An empty binary tree is denoted by None. A non-empty tree is denoted as (X, L, R), where X is the value contained in the root and L and R denote the left and right subtrees, respectively. The tree from the above figure can be denoted as:
(5, (3, (20, (6, None, None), None), None), (10, (1, None, None), (15, (30, None, (9, None, None)), (8, None, None))))Assumptions
Write an efficient algorithm for the following assumptions:
- N is an integer within the range [1..100,000];
- the height of tree T (number of edges on the longest path from root to leaf) is within the range [0..800].
Copyright 2009–2025 by Codility Limited. All Rights Reserved. Unauthorized copying, publication or disclosure prohibited.
In this problem we consider binary trees. Let's define a turn on a path as a change in the direction of the path (i.e. a switch from right to left or vice versa). A zigzag is simply a sequence of turns (it can start with either right or left). The length of a zigzag is equal to the number of turns.
Consider binary tree below:
There are two turns on the marked path. The first one is at [15]; the second is at [30]. That means that the length of this zigzag is equal to 2. This is also the longest zigzag in the tree under consideration. In this problem you should find the longest zigzag that starts at the root of any given binary tree and form a downwards path.
Note that a zigzag containing only one edge or one node has length 0.
Problem
Write a function:
function solution(T: Tree): longint;
that, given a non-empty binary tree T consisting of N nodes, returns the length of the longest zigzag starting at the root.
For example, given tree T shown in the figure above, the function should return 2, as explained above. Note that the values contained in the nodes are not relevant in this task.
Technical details
A binary tree can be specified using a pointer data structure. Assume that the following declarations are given:
Tree = ^TreeNode; TreeNode = record x : longint; l : Tree; r : Tree; end;
An empty tree is represented by an empty pointer (denoted by nil). A non-empty tree is represented by a pointer to an object representing its root. The attribute x holds the integer contained in the root, whereas attributes l and r hold the left and right subtrees of the binary tree, respectively.
For the purpose of entering your own test cases, you can denote a tree recursively in the following way. An empty binary tree is denoted by None. A non-empty tree is denoted as (X, L, R), where X is the value contained in the root and L and R denote the left and right subtrees, respectively. The tree from the above figure can be denoted as:
(5, (3, (20, (6, None, None), None), None), (10, (1, None, None), (15, (30, None, (9, None, None)), (8, None, None))))Assumptions
Write an efficient algorithm for the following assumptions:
- N is an integer within the range [1..100,000];
- the height of tree T (number of edges on the longest path from root to leaf) is within the range [0..800].
Copyright 2009–2025 by Codility Limited. All Rights Reserved. Unauthorized copying, publication or disclosure prohibited.
In this problem we consider binary trees. Let's define a turn on a path as a change in the direction of the path (i.e. a switch from right to left or vice versa). A zigzag is simply a sequence of turns (it can start with either right or left). The length of a zigzag is equal to the number of turns.
Consider binary tree below:
There are two turns on the marked path. The first one is at [15]; the second is at [30]. That means that the length of this zigzag is equal to 2. This is also the longest zigzag in the tree under consideration. In this problem you should find the longest zigzag that starts at the root of any given binary tree and form a downwards path.
Note that a zigzag containing only one edge or one node has length 0.
Problem
Write a function:
function solution($T);
that, given a non-empty binary tree T consisting of N nodes, returns the length of the longest zigzag starting at the root.
For example, given tree T shown in the figure above, the function should return 2, as explained above. Note that the values contained in the nodes are not relevant in this task.
Technical details
A binary tree can be specified using a pointer data structure. Assume that the following declarations are given:
class Tree { var $x = 0; var $l = NULL; var $r = NULL; }
An empty tree is represented by an empty pointer (denoted by NULL). A non-empty tree is represented by a pointer to an object representing its root. The attribute x holds the integer contained in the root, whereas attributes l and r hold the left and right subtrees of the binary tree, respectively.
For the purpose of entering your own test cases, you can denote a tree recursively in the following way. An empty binary tree is denoted by None. A non-empty tree is denoted as (X, L, R), where X is the value contained in the root and L and R denote the left and right subtrees, respectively. The tree from the above figure can be denoted as:
(5, (3, (20, (6, None, None), None), None), (10, (1, None, None), (15, (30, None, (9, None, None)), (8, None, None))))Assumptions
Write an efficient algorithm for the following assumptions:
- N is an integer within the range [1..100,000];
- the height of tree T (number of edges on the longest path from root to leaf) is within the range [0..800].
Copyright 2009–2025 by Codility Limited. All Rights Reserved. Unauthorized copying, publication or disclosure prohibited.
In this problem we consider binary trees. Let's define a turn on a path as a change in the direction of the path (i.e. a switch from right to left or vice versa). A zigzag is simply a sequence of turns (it can start with either right or left). The length of a zigzag is equal to the number of turns.
Consider binary tree below:
There are two turns on the marked path. The first one is at [15]; the second is at [30]. That means that the length of this zigzag is equal to 2. This is also the longest zigzag in the tree under consideration. In this problem you should find the longest zigzag that starts at the root of any given binary tree and form a downwards path.
Note that a zigzag containing only one edge or one node has length 0.
Problem
Write a function:
sub solution { my ($T) = @_; ... }
that, given a non-empty binary tree T consisting of N nodes, returns the length of the longest zigzag starting at the root.
For example, given tree T shown in the figure above, the function should return 2, as explained above. Note that the values contained in the nodes are not relevant in this task.
Technical details
A binary tree can be specified using a pointer data structure. Assume that the following declarations are given:
# Tree is a dictionary with keys # 'x' - type: int # 'l' - type: Tree # 'r' - type: Tree
An empty tree is represented by an empty pointer (denoted by undef). A non-empty tree is represented by a pointer to an object representing its root. The attribute x holds the integer contained in the root, whereas attributes l and r hold the left and right subtrees of the binary tree, respectively.
For the purpose of entering your own test cases, you can denote a tree recursively in the following way. An empty binary tree is denoted by None. A non-empty tree is denoted as (X, L, R), where X is the value contained in the root and L and R denote the left and right subtrees, respectively. The tree from the above figure can be denoted as:
(5, (3, (20, (6, None, None), None), None), (10, (1, None, None), (15, (30, None, (9, None, None)), (8, None, None))))Assumptions
Write an efficient algorithm for the following assumptions:
- N is an integer within the range [1..100,000];
- the height of tree T (number of edges on the longest path from root to leaf) is within the range [0..800].
Copyright 2009–2025 by Codility Limited. All Rights Reserved. Unauthorized copying, publication or disclosure prohibited.
In this problem we consider binary trees. Let's define a turn on a path as a change in the direction of the path (i.e. a switch from right to left or vice versa). A zigzag is simply a sequence of turns (it can start with either right or left). The length of a zigzag is equal to the number of turns.
Consider binary tree below:
There are two turns on the marked path. The first one is at [15]; the second is at [30]. That means that the length of this zigzag is equal to 2. This is also the longest zigzag in the tree under consideration. In this problem you should find the longest zigzag that starts at the root of any given binary tree and form a downwards path.
Note that a zigzag containing only one edge or one node has length 0.
Problem
Write a function:
def solution(T)
that, given a non-empty binary tree T consisting of N nodes, returns the length of the longest zigzag starting at the root.
For example, given tree T shown in the figure above, the function should return 2, as explained above. Note that the values contained in the nodes are not relevant in this task.
Technical details
A binary tree can be specified using a pointer data structure. Assume that the following declarations are given:
from dataclasses import dataclass, field @dataclass class Tree: x: int = 0 l: "Tree" = None r: "Tree" = None
An empty tree is represented by an empty pointer (denoted by None). A non-empty tree is represented by a pointer to an object representing its root. The attribute x holds the integer contained in the root, whereas attributes l and r hold the left and right subtrees of the binary tree, respectively.
For the purpose of entering your own test cases, you can denote a tree recursively in the following way. An empty binary tree is denoted by None. A non-empty tree is denoted as (X, L, R), where X is the value contained in the root and L and R denote the left and right subtrees, respectively. The tree from the above figure can be denoted as:
(5, (3, (20, (6, None, None), None), None), (10, (1, None, None), (15, (30, None, (9, None, None)), (8, None, None))))Assumptions
Write an efficient algorithm for the following assumptions:
- N is an integer within the range [1..100,000];
- the height of tree T (number of edges on the longest path from root to leaf) is within the range [0..800].
Copyright 2009–2025 by Codility Limited. All Rights Reserved. Unauthorized copying, publication or disclosure prohibited.
In this problem we consider binary trees. Let's define a turn on a path as a change in the direction of the path (i.e. a switch from right to left or vice versa). A zigzag is simply a sequence of turns (it can start with either right or left). The length of a zigzag is equal to the number of turns.
Consider binary tree below:
There are two turns on the marked path. The first one is at [15]; the second is at [30]. That means that the length of this zigzag is equal to 2. This is also the longest zigzag in the tree under consideration. In this problem you should find the longest zigzag that starts at the root of any given binary tree and form a downwards path.
Note that a zigzag containing only one edge or one node has length 0.
Problem
Write a function:
def solution(t)
that, given a non-empty binary tree T consisting of N nodes, returns the length of the longest zigzag starting at the root.
For example, given tree T shown in the figure above, the function should return 2, as explained above. Note that the values contained in the nodes are not relevant in this task.
Technical details
A binary tree can be specified using a pointer data structure. Assume that the following declarations are given:
class Tree attr_accessor :x, :l, :r end
An empty tree is represented by an empty pointer (denoted by nil). A non-empty tree is represented by a pointer to an object representing its root. The attribute x holds the integer contained in the root, whereas attributes l and r hold the left and right subtrees of the binary tree, respectively.
For the purpose of entering your own test cases, you can denote a tree recursively in the following way. An empty binary tree is denoted by None. A non-empty tree is denoted as (X, L, R), where X is the value contained in the root and L and R denote the left and right subtrees, respectively. The tree from the above figure can be denoted as:
(5, (3, (20, (6, None, None), None), None), (10, (1, None, None), (15, (30, None, (9, None, None)), (8, None, None))))Assumptions
Write an efficient algorithm for the following assumptions:
- N is an integer within the range [1..100,000];
- the height of tree T (number of edges on the longest path from root to leaf) is within the range [0..800].
Copyright 2009–2025 by Codility Limited. All Rights Reserved. Unauthorized copying, publication or disclosure prohibited.
In this problem we consider binary trees. Let's define a turn on a path as a change in the direction of the path (i.e. a switch from right to left or vice versa). A zigzag is simply a sequence of turns (it can start with either right or left). The length of a zigzag is equal to the number of turns.
Consider binary tree below:
There are two turns on the marked path. The first one is at [15]; the second is at [30]. That means that the length of this zigzag is equal to 2. This is also the longest zigzag in the tree under consideration. In this problem you should find the longest zigzag that starts at the root of any given binary tree and form a downwards path.
Note that a zigzag containing only one edge or one node has length 0.
Problem
Write a function:
object Solution { def solution(t: Tree): Int }
that, given a non-empty binary tree T consisting of N nodes, returns the length of the longest zigzag starting at the root.
For example, given tree T shown in the figure above, the function should return 2, as explained above. Note that the values contained in the nodes are not relevant in this task.
Technical details
A binary tree can be specified using a pointer data structure. Assume that the following declarations are given:
class Tree(var x: Int, var l: Tree, var r: Tree)
An empty tree is represented by an empty pointer (denoted by null). A non-empty tree is represented by a pointer to an object representing its root. The attribute x holds the integer contained in the root, whereas attributes l and r hold the left and right subtrees of the binary tree, respectively.
For the purpose of entering your own test cases, you can denote a tree recursively in the following way. An empty binary tree is denoted by None. A non-empty tree is denoted as (X, L, R), where X is the value contained in the root and L and R denote the left and right subtrees, respectively. The tree from the above figure can be denoted as:
(5, (3, (20, (6, None, None), None), None), (10, (1, None, None), (15, (30, None, (9, None, None)), (8, None, None))))Assumptions
Write an efficient algorithm for the following assumptions:
- N is an integer within the range [1..100,000];
- the height of tree T (number of edges on the longest path from root to leaf) is within the range [0..800].
Copyright 2009–2025 by Codility Limited. All Rights Reserved. Unauthorized copying, publication or disclosure prohibited.
In this problem we consider binary trees. Let's define a turn on a path as a change in the direction of the path (i.e. a switch from right to left or vice versa). A zigzag is simply a sequence of turns (it can start with either right or left). The length of a zigzag is equal to the number of turns.
Consider binary tree below:
There are two turns on the marked path. The first one is at [15]; the second is at [30]. That means that the length of this zigzag is equal to 2. This is also the longest zigzag in the tree under consideration. In this problem you should find the longest zigzag that starts at the root of any given binary tree and form a downwards path.
Note that a zigzag containing only one edge or one node has length 0.
Problem
Write a function:
public func solution(_ T : Tree?) -> Int
that, given a non-empty binary tree T consisting of N nodes, returns the length of the longest zigzag starting at the root.
For example, given tree T shown in the figure above, the function should return 2, as explained above. Note that the values contained in the nodes are not relevant in this task.
Technical details
A binary tree can be specified using a pointer data structure. Assume that the following declarations are given:
public class Tree { public var x : Int = 0 public var l : Tree? public var r : Tree? public init() {} }
An empty tree is represented by an empty pointer (denoted by nil). A non-empty tree is represented by a pointer to an object representing its root. The attribute x holds the integer contained in the root, whereas attributes l and r hold the left and right subtrees of the binary tree, respectively.
For the purpose of entering your own test cases, you can denote a tree recursively in the following way. An empty binary tree is denoted by None. A non-empty tree is denoted as (X, L, R), where X is the value contained in the root and L and R denote the left and right subtrees, respectively. The tree from the above figure can be denoted as:
(5, (3, (20, (6, None, None), None), None), (10, (1, None, None), (15, (30, None, (9, None, None)), (8, None, None))))Assumptions
Write an efficient algorithm for the following assumptions:
- N is an integer within the range [1..100,000];
- the height of tree T (number of edges on the longest path from root to leaf) is within the range [0..800].
Copyright 2009–2025 by Codility Limited. All Rights Reserved. Unauthorized copying, publication or disclosure prohibited.
In this problem we consider binary trees. Let's define a turn on a path as a change in the direction of the path (i.e. a switch from right to left or vice versa). A zigzag is simply a sequence of turns (it can start with either right or left). The length of a zigzag is equal to the number of turns.
Consider binary tree below:
There are two turns on the marked path. The first one is at [15]; the second is at [30]. That means that the length of this zigzag is equal to 2. This is also the longest zigzag in the tree under consideration. In this problem you should find the longest zigzag that starts at the root of any given binary tree and form a downwards path.
Note that a zigzag containing only one edge or one node has length 0.
Problem
Write a function:
function solution(T: Tree): number;
that, given a non-empty binary tree T consisting of N nodes, returns the length of the longest zigzag starting at the root.
For example, given tree T shown in the figure above, the function should return 2, as explained above. Note that the values contained in the nodes are not relevant in this task.
Technical details
A binary tree can be specified using a pointer data structure. Assume that the following declarations are given:
class Tree { x: number; l: Tree; r: Tree; constructor(x: number = 0, l: Tree = null, r: Tree = null) { this.x = x; this.l = l; this.r = r; } }
An empty tree is represented by an empty pointer (denoted by null). A non-empty tree is represented by a pointer to an object representing its root. The attribute x holds the integer contained in the root, whereas attributes l and r hold the left and right subtrees of the binary tree, respectively.
For the purpose of entering your own test cases, you can denote a tree recursively in the following way. An empty binary tree is denoted by None. A non-empty tree is denoted as (X, L, R), where X is the value contained in the root and L and R denote the left and right subtrees, respectively. The tree from the above figure can be denoted as:
(5, (3, (20, (6, None, None), None), None), (10, (1, None, None), (15, (30, None, (9, None, None)), (8, None, None))))Assumptions
Write an efficient algorithm for the following assumptions:
- N is an integer within the range [1..100,000];
- the height of tree T (number of edges on the longest path from root to leaf) is within the range [0..800].
Copyright 2009–2025 by Codility Limited. All Rights Reserved. Unauthorized copying, publication or disclosure prohibited.
In this problem we consider binary trees. Let's define a turn on a path as a change in the direction of the path (i.e. a switch from right to left or vice versa). A zigzag is simply a sequence of turns (it can start with either right or left). The length of a zigzag is equal to the number of turns.
Consider binary tree below:
There are two turns on the marked path. The first one is at [15]; the second is at [30]. That means that the length of this zigzag is equal to 2. This is also the longest zigzag in the tree under consideration. In this problem you should find the longest zigzag that starts at the root of any given binary tree and form a downwards path.
Note that a zigzag containing only one edge or one node has length 0.
Problem
Write a function:
Private Function solution(T As Tree) As Integer
that, given a non-empty binary tree T consisting of N nodes, returns the length of the longest zigzag starting at the root.
For example, given tree T shown in the figure above, the function should return 2, as explained above. Note that the values contained in the nodes are not relevant in this task.
Technical details
A binary tree can be specified using a pointer data structure. Assume that the following declarations are given:
Class Tree Public x As Integer Public l As Tree Public r As Tree End Class
An empty tree is represented by an empty pointer (denoted by Nothing). A non-empty tree is represented by a pointer to an object representing its root. The attribute x holds the integer contained in the root, whereas attributes l and r hold the left and right subtrees of the binary tree, respectively.
For the purpose of entering your own test cases, you can denote a tree recursively in the following way. An empty binary tree is denoted by None. A non-empty tree is denoted as (X, L, R), where X is the value contained in the root and L and R denote the left and right subtrees, respectively. The tree from the above figure can be denoted as:
(5, (3, (20, (6, None, None), None), None), (10, (1, None, None), (15, (30, None, (9, None, None)), (8, None, None))))Assumptions
Write an efficient algorithm for the following assumptions:
- N is an integer within the range [1..100,000];
- the height of tree T (number of edges on the longest path from root to leaf) is within the range [0..800].
Copyright 2009–2025 by Codility Limited. All Rights Reserved. Unauthorized copying, publication or disclosure prohibited.
W tym zadaniu rozwa偶amy 艣cie偶ki w drzewie binarnym, biegn膮ce z korzenia w d贸艂. Zdefiniujmy zwrot na 艣cie偶ce jako zmian臋 w jej kierunku (z prawa na lewo lub odwrotnie). Zygzak to po prostu ci膮g zwrot贸w na pewnej 艣cie偶ce (kt贸ra mo偶e zaczyna膰 si臋 od kierunku w prawo lub w lewo). D艂ugo艣膰 zygzaka to liczba zwrot贸w.
Rozwa偶my nast臋puj膮ce drzewo binarne:
Zaznaczona 艣cie偶ka ma dwa zwroty, kolejno w wierzcho艂kach [15] oraz [30], wi臋c jest to zygzak o d艂ugo艣ci 2, kt贸ry r贸wnocze艣nie jest te偶 najd艂u偶szym zygzakiem w tym drzewie. Twoim zadaniem jest znalezienie d艂ugo艣ci najd艂u偶szego zygzaka zaczynaj膮cego si臋 w korzeniu danego drzewa.
Zygzak sk艂adaj膮cy si臋 tylko z jednej kraw臋dzi lub jednego w臋z艂a ma d艂ugo艣膰 0.
Problem
Napisz funkcj臋:
int solution(struct tree * T);
kt贸ra, maj膮c dane niepuste drzewo binarne T zawieraj膮ce N w臋z艂贸w, zwraca d艂ugo艣膰 najd艂u偶szego zygzaka zaczynaj膮cego si臋 w korzeniu.
Na przyk艂ad, maj膮c dane drzewo pokazane na rysunku powy偶ej, funkcja powinna zwr贸ci膰 2, tak jak zosta艂o to wyja艣nione wcze艣niej. Warto艣ci znajduj膮ce si臋 w w臋z艂ach nie s膮 istotne w tym zadaniu.
Szczeg贸艂y techniczne
Drzewo binarne jest dane jako wska藕nikowa struktura danych. Mo偶esz za艂o偶y膰, 偶e nast臋puj膮ce deklaracje zosta艂y zdefiniowane:
struct tree { int x; struct tree * l; struct tree * r; };
Puste drzewo jest reprezentowane przez pusty wska藕nik (oznaczany jako NULL). Niepuste drzewo jest reprezentowane przez wska藕nik do obiektu reprezentuj膮cego korze艅. Atrybut x zawiera liczb臋 ca艂kowit膮 znajduj膮c膮 si臋 w korzeniu, natomiast atrybuty l i r to, odpowiednio, lewe i prawe poddrzewo drzewa binarnego.
Na potrzeby wprowadzania swoich w艂asnych test贸w, mo偶esz opisywa膰 drzewa rekurencyjnie w nast臋puj膮cy spos贸b. Puste drzewo binarne jest oznaczane przez None. Niepuste drzewo binarne jest oznaczane przez (X, L, R), gdzie X to warto艣膰 znajduj膮ca si臋 w korzeniu, a L i R oznaczaj膮, odpowiednio, lewe i prawe poddrzewo. Drzewo przedstawione na rysunku powy偶ej mo偶e by膰 przedstawione jako:
(5, (3, (20, (6, None, None), None), None), (10, (1, None, None), (15, (30, None, (9, None, None)), (8, None, None))))Za艂o偶enia
Za艂o偶enia:
- N to liczba ca艂kowita z przedzia艂u [1..100,000];
- wysoko艣膰 drzewa T (liczba kraw臋dzi na najd艂u偶szej 艣cie偶ce od korzenia do li艣cia) jest z przedzia艂u [0..800].
Copyright 2009–2025 by Codility Limited. All Rights Reserved. Unauthorized copying, publication or disclosure prohibited.
W tym zadaniu rozwa偶amy 艣cie偶ki w drzewie binarnym, biegn膮ce z korzenia w d贸艂. Zdefiniujmy zwrot na 艣cie偶ce jako zmian臋 w jej kierunku (z prawa na lewo lub odwrotnie). Zygzak to po prostu ci膮g zwrot贸w na pewnej 艣cie偶ce (kt贸ra mo偶e zaczyna膰 si臋 od kierunku w prawo lub w lewo). D艂ugo艣膰 zygzaka to liczba zwrot贸w.
Rozwa偶my nast臋puj膮ce drzewo binarne:
Zaznaczona 艣cie偶ka ma dwa zwroty, kolejno w wierzcho艂kach [15] oraz [30], wi臋c jest to zygzak o d艂ugo艣ci 2, kt贸ry r贸wnocze艣nie jest te偶 najd艂u偶szym zygzakiem w tym drzewie. Twoim zadaniem jest znalezienie d艂ugo艣ci najd艂u偶szego zygzaka zaczynaj膮cego si臋 w korzeniu danego drzewa.
Zygzak sk艂adaj膮cy si臋 tylko z jednej kraw臋dzi lub jednego w臋z艂a ma d艂ugo艣膰 0.
Problem
Napisz funkcj臋:
int solution(tree * T);
kt贸ra, maj膮c dane niepuste drzewo binarne T zawieraj膮ce N w臋z艂贸w, zwraca d艂ugo艣膰 najd艂u偶szego zygzaka zaczynaj膮cego si臋 w korzeniu.
Na przyk艂ad, maj膮c dane drzewo pokazane na rysunku powy偶ej, funkcja powinna zwr贸ci膰 2, tak jak zosta艂o to wyja艣nione wcze艣niej. Warto艣ci znajduj膮ce si臋 w w臋z艂ach nie s膮 istotne w tym zadaniu.
Szczeg贸艂y techniczne
Drzewo binarne jest dane jako wska藕nikowa struktura danych. Mo偶esz za艂o偶y膰, 偶e nast臋puj膮ce deklaracje zosta艂y zdefiniowane:
struct tree { int x; tree * l; tree * r; };
Puste drzewo jest reprezentowane przez pusty wska藕nik (oznaczany jako nullptr). Niepuste drzewo jest reprezentowane przez wska藕nik do obiektu reprezentuj膮cego korze艅. Atrybut x zawiera liczb臋 ca艂kowit膮 znajduj膮c膮 si臋 w korzeniu, natomiast atrybuty l i r to, odpowiednio, lewe i prawe poddrzewo drzewa binarnego.
Na potrzeby wprowadzania swoich w艂asnych test贸w, mo偶esz opisywa膰 drzewa rekurencyjnie w nast臋puj膮cy spos贸b. Puste drzewo binarne jest oznaczane przez None. Niepuste drzewo binarne jest oznaczane przez (X, L, R), gdzie X to warto艣膰 znajduj膮ca si臋 w korzeniu, a L i R oznaczaj膮, odpowiednio, lewe i prawe poddrzewo. Drzewo przedstawione na rysunku powy偶ej mo偶e by膰 przedstawione jako:
(5, (3, (20, (6, None, None), None), None), (10, (1, None, None), (15, (30, None, (9, None, None)), (8, None, None))))Za艂o偶enia
Za艂o偶enia:
- N to liczba ca艂kowita z przedzia艂u [1..100,000];
- wysoko艣膰 drzewa T (liczba kraw臋dzi na najd艂u偶szej 艣cie偶ce od korzenia do li艣cia) jest z przedzia艂u [0..800].
Copyright 2009–2025 by Codility Limited. All Rights Reserved. Unauthorized copying, publication or disclosure prohibited.
W tym zadaniu rozwa偶amy 艣cie偶ki w drzewie binarnym, biegn膮ce z korzenia w d贸艂. Zdefiniujmy zwrot na 艣cie偶ce jako zmian臋 w jej kierunku (z prawa na lewo lub odwrotnie). Zygzak to po prostu ci膮g zwrot贸w na pewnej 艣cie偶ce (kt贸ra mo偶e zaczyna膰 si臋 od kierunku w prawo lub w lewo). D艂ugo艣膰 zygzaka to liczba zwrot贸w.
Rozwa偶my nast臋puj膮ce drzewo binarne:
Zaznaczona 艣cie偶ka ma dwa zwroty, kolejno w wierzcho艂kach [15] oraz [30], wi臋c jest to zygzak o d艂ugo艣ci 2, kt贸ry r贸wnocze艣nie jest te偶 najd艂u偶szym zygzakiem w tym drzewie. Twoim zadaniem jest znalezienie d艂ugo艣ci najd艂u偶szego zygzaka zaczynaj膮cego si臋 w korzeniu danego drzewa.
Zygzak sk艂adaj膮cy si臋 tylko z jednej kraw臋dzi lub jednego w臋z艂a ma d艂ugo艣膰 0.
Problem
Napisz funkcj臋:
class Solution { public int solution(Tree T); }
kt贸ra, maj膮c dane niepuste drzewo binarne T zawieraj膮ce N w臋z艂贸w, zwraca d艂ugo艣膰 najd艂u偶szego zygzaka zaczynaj膮cego si臋 w korzeniu.
Na przyk艂ad, maj膮c dane drzewo pokazane na rysunku powy偶ej, funkcja powinna zwr贸ci膰 2, tak jak zosta艂o to wyja艣nione wcze艣niej. Warto艣ci znajduj膮ce si臋 w w臋z艂ach nie s膮 istotne w tym zadaniu.
Szczeg贸艂y techniczne
Drzewo binarne jest dane jako wska藕nikowa struktura danych. Mo偶esz za艂o偶y膰, 偶e nast臋puj膮ce deklaracje zosta艂y zdefiniowane:
class Tree { public int x; public Tree l; public Tree r; };
Puste drzewo jest reprezentowane przez pusty wska藕nik (oznaczany jako null). Niepuste drzewo jest reprezentowane przez wska藕nik do obiektu reprezentuj膮cego korze艅. Atrybut x zawiera liczb臋 ca艂kowit膮 znajduj膮c膮 si臋 w korzeniu, natomiast atrybuty l i r to, odpowiednio, lewe i prawe poddrzewo drzewa binarnego.
Na potrzeby wprowadzania swoich w艂asnych test贸w, mo偶esz opisywa膰 drzewa rekurencyjnie w nast臋puj膮cy spos贸b. Puste drzewo binarne jest oznaczane przez None. Niepuste drzewo binarne jest oznaczane przez (X, L, R), gdzie X to warto艣膰 znajduj膮ca si臋 w korzeniu, a L i R oznaczaj膮, odpowiednio, lewe i prawe poddrzewo. Drzewo przedstawione na rysunku powy偶ej mo偶e by膰 przedstawione jako:
(5, (3, (20, (6, None, None), None), None), (10, (1, None, None), (15, (30, None, (9, None, None)), (8, None, None))))Za艂o偶enia
Za艂o偶enia:
- N to liczba ca艂kowita z przedzia艂u [1..100,000];
- wysoko艣膰 drzewa T (liczba kraw臋dzi na najd艂u偶szej 艣cie偶ce od korzenia do li艣cia) jest z przedzia艂u [0..800].
Copyright 2009–2025 by Codility Limited. All Rights Reserved. Unauthorized copying, publication or disclosure prohibited.
W tym zadaniu rozwa偶amy 艣cie偶ki w drzewie binarnym, biegn膮ce z korzenia w d贸艂. Zdefiniujmy zwrot na 艣cie偶ce jako zmian臋 w jej kierunku (z prawa na lewo lub odwrotnie). Zygzak to po prostu ci膮g zwrot贸w na pewnej 艣cie偶ce (kt贸ra mo偶e zaczyna膰 si臋 od kierunku w prawo lub w lewo). D艂ugo艣膰 zygzaka to liczba zwrot贸w.
Rozwa偶my nast臋puj膮ce drzewo binarne:
Zaznaczona 艣cie偶ka ma dwa zwroty, kolejno w wierzcho艂kach [15] oraz [30], wi臋c jest to zygzak o d艂ugo艣ci 2, kt贸ry r贸wnocze艣nie jest te偶 najd艂u偶szym zygzakiem w tym drzewie. Twoim zadaniem jest znalezienie d艂ugo艣ci najd艂u偶szego zygzaka zaczynaj膮cego si臋 w korzeniu danego drzewa.
Zygzak sk艂adaj膮cy si臋 tylko z jednej kraw臋dzi lub jednego w臋z艂a ma d艂ugo艣膰 0.
Problem
Napisz funkcj臋:
int solution(Tree? T);
kt贸ra, maj膮c dane niepuste drzewo binarne T zawieraj膮ce N w臋z艂贸w, zwraca d艂ugo艣膰 najd艂u偶szego zygzaka zaczynaj膮cego si臋 w korzeniu.
Na przyk艂ad, maj膮c dane drzewo pokazane na rysunku powy偶ej, funkcja powinna zwr贸ci膰 2, tak jak zosta艂o to wyja艣nione wcze艣niej. Warto艣ci znajduj膮ce si臋 w w臋z艂ach nie s膮 istotne w tym zadaniu.
Szczeg贸艂y techniczne
Drzewo binarne jest dane jako wska藕nikowa struktura danych. Mo偶esz za艂o偶y膰, 偶e nast臋puj膮ce deklaracje zosta艂y zdefiniowane:
class Tree { int x = 0; Tree? l = null; Tree? r = null; }
Puste drzewo jest reprezentowane przez pusty wska藕nik (oznaczany jako null). Niepuste drzewo jest reprezentowane przez wska藕nik do obiektu reprezentuj膮cego korze艅. Atrybut x zawiera liczb臋 ca艂kowit膮 znajduj膮c膮 si臋 w korzeniu, natomiast atrybuty l i r to, odpowiednio, lewe i prawe poddrzewo drzewa binarnego.
Na potrzeby wprowadzania swoich w艂asnych test贸w, mo偶esz opisywa膰 drzewa rekurencyjnie w nast臋puj膮cy spos贸b. Puste drzewo binarne jest oznaczane przez None. Niepuste drzewo binarne jest oznaczane przez (X, L, R), gdzie X to warto艣膰 znajduj膮ca si臋 w korzeniu, a L i R oznaczaj膮, odpowiednio, lewe i prawe poddrzewo. Drzewo przedstawione na rysunku powy偶ej mo偶e by膰 przedstawione jako:
(5, (3, (20, (6, None, None), None), None), (10, (1, None, None), (15, (30, None, (9, None, None)), (8, None, None))))Za艂o偶enia
Za艂o偶enia:
- N to liczba ca艂kowita z przedzia艂u [1..100,000];
- wysoko艣膰 drzewa T (liczba kraw臋dzi na najd艂u偶szej 艣cie偶ce od korzenia do li艣cia) jest z przedzia艂u [0..800].
Copyright 2009–2025 by Codility Limited. All Rights Reserved. Unauthorized copying, publication or disclosure prohibited.
W tym zadaniu rozwa偶amy 艣cie偶ki w drzewie binarnym, biegn膮ce z korzenia w d贸艂. Zdefiniujmy zwrot na 艣cie偶ce jako zmian臋 w jej kierunku (z prawa na lewo lub odwrotnie). Zygzak to po prostu ci膮g zwrot贸w na pewnej 艣cie偶ce (kt贸ra mo偶e zaczyna膰 si臋 od kierunku w prawo lub w lewo). D艂ugo艣膰 zygzaka to liczba zwrot贸w.
Rozwa偶my nast臋puj膮ce drzewo binarne:
Zaznaczona 艣cie偶ka ma dwa zwroty, kolejno w wierzcho艂kach [15] oraz [30], wi臋c jest to zygzak o d艂ugo艣ci 2, kt贸ry r贸wnocze艣nie jest te偶 najd艂u偶szym zygzakiem w tym drzewie. Twoim zadaniem jest znalezienie d艂ugo艣ci najd艂u偶szego zygzaka zaczynaj膮cego si臋 w korzeniu danego drzewa.
Zygzak sk艂adaj膮cy si臋 tylko z jednej kraw臋dzi lub jednego w臋z艂a ma d艂ugo艣膰 0.
Problem
Napisz funkcj臋:
func Solution(T *Tree) int
kt贸ra, maj膮c dane niepuste drzewo binarne T zawieraj膮ce N w臋z艂贸w, zwraca d艂ugo艣膰 najd艂u偶szego zygzaka zaczynaj膮cego si臋 w korzeniu.
Na przyk艂ad, maj膮c dane drzewo pokazane na rysunku powy偶ej, funkcja powinna zwr贸ci膰 2, tak jak zosta艂o to wyja艣nione wcze艣niej. Warto艣ci znajduj膮ce si臋 w w臋z艂ach nie s膮 istotne w tym zadaniu.
Szczeg贸艂y techniczne
Drzewo binarne jest dane jako wska藕nikowa struktura danych. Mo偶esz za艂o偶y膰, 偶e nast臋puj膮ce deklaracje zosta艂y zdefiniowane:
type Tree struct { X int L *Tree R *Tree }
Puste drzewo jest reprezentowane przez pusty wska藕nik (oznaczany jako nil). Niepuste drzewo jest reprezentowane przez wska藕nik do obiektu reprezentuj膮cego korze艅. Atrybut x zawiera liczb臋 ca艂kowit膮 znajduj膮c膮 si臋 w korzeniu, natomiast atrybuty l i r to, odpowiednio, lewe i prawe poddrzewo drzewa binarnego.
Na potrzeby wprowadzania swoich w艂asnych test贸w, mo偶esz opisywa膰 drzewa rekurencyjnie w nast臋puj膮cy spos贸b. Puste drzewo binarne jest oznaczane przez None. Niepuste drzewo binarne jest oznaczane przez (X, L, R), gdzie X to warto艣膰 znajduj膮ca si臋 w korzeniu, a L i R oznaczaj膮, odpowiednio, lewe i prawe poddrzewo. Drzewo przedstawione na rysunku powy偶ej mo偶e by膰 przedstawione jako:
(5, (3, (20, (6, None, None), None), None), (10, (1, None, None), (15, (30, None, (9, None, None)), (8, None, None))))Za艂o偶enia
Za艂o偶enia:
- N to liczba ca艂kowita z przedzia艂u [1..100,000];
- wysoko艣膰 drzewa T (liczba kraw臋dzi na najd艂u偶szej 艣cie偶ce od korzenia do li艣cia) jest z przedzia艂u [0..800].
Copyright 2009–2025 by Codility Limited. All Rights Reserved. Unauthorized copying, publication or disclosure prohibited.
W tym zadaniu rozwa偶amy 艣cie偶ki w drzewie binarnym, biegn膮ce z korzenia w d贸艂. Zdefiniujmy zwrot na 艣cie偶ce jako zmian臋 w jej kierunku (z prawa na lewo lub odwrotnie). Zygzak to po prostu ci膮g zwrot贸w na pewnej 艣cie偶ce (kt贸ra mo偶e zaczyna膰 si臋 od kierunku w prawo lub w lewo). D艂ugo艣膰 zygzaka to liczba zwrot贸w.
Rozwa偶my nast臋puj膮ce drzewo binarne:
Zaznaczona 艣cie偶ka ma dwa zwroty, kolejno w wierzcho艂kach [15] oraz [30], wi臋c jest to zygzak o d艂ugo艣ci 2, kt贸ry r贸wnocze艣nie jest te偶 najd艂u偶szym zygzakiem w tym drzewie. Twoim zadaniem jest znalezienie d艂ugo艣ci najd艂u偶szego zygzaka zaczynaj膮cego si臋 w korzeniu danego drzewa.
Zygzak sk艂adaj膮cy si臋 tylko z jednej kraw臋dzi lub jednego w臋z艂a ma d艂ugo艣膰 0.
Problem
Napisz funkcj臋:
class Solution { public int solution(Tree T); }
kt贸ra, maj膮c dane niepuste drzewo binarne T zawieraj膮ce N w臋z艂贸w, zwraca d艂ugo艣膰 najd艂u偶szego zygzaka zaczynaj膮cego si臋 w korzeniu.
Na przyk艂ad, maj膮c dane drzewo pokazane na rysunku powy偶ej, funkcja powinna zwr贸ci膰 2, tak jak zosta艂o to wyja艣nione wcze艣niej. Warto艣ci znajduj膮ce si臋 w w臋z艂ach nie s膮 istotne w tym zadaniu.
Szczeg贸艂y techniczne
Drzewo binarne jest dane jako wska藕nikowa struktura danych. Mo偶esz za艂o偶y膰, 偶e nast臋puj膮ce deklaracje zosta艂y zdefiniowane:
class Tree { public int x; public Tree l; public Tree r; }
Puste drzewo jest reprezentowane przez pusty wska藕nik (oznaczany jako null). Niepuste drzewo jest reprezentowane przez wska藕nik do obiektu reprezentuj膮cego korze艅. Atrybut x zawiera liczb臋 ca艂kowit膮 znajduj膮c膮 si臋 w korzeniu, natomiast atrybuty l i r to, odpowiednio, lewe i prawe poddrzewo drzewa binarnego.
Na potrzeby wprowadzania swoich w艂asnych test贸w, mo偶esz opisywa膰 drzewa rekurencyjnie w nast臋puj膮cy spos贸b. Puste drzewo binarne jest oznaczane przez None. Niepuste drzewo binarne jest oznaczane przez (X, L, R), gdzie X to warto艣膰 znajduj膮ca si臋 w korzeniu, a L i R oznaczaj膮, odpowiednio, lewe i prawe poddrzewo. Drzewo przedstawione na rysunku powy偶ej mo偶e by膰 przedstawione jako:
(5, (3, (20, (6, None, None), None), None), (10, (1, None, None), (15, (30, None, (9, None, None)), (8, None, None))))Za艂o偶enia
Za艂o偶enia:
- N to liczba ca艂kowita z przedzia艂u [1..100,000];
- wysoko艣膰 drzewa T (liczba kraw臋dzi na najd艂u偶szej 艣cie偶ce od korzenia do li艣cia) jest z przedzia艂u [0..800].
Copyright 2009–2025 by Codility Limited. All Rights Reserved. Unauthorized copying, publication or disclosure prohibited.
W tym zadaniu rozwa偶amy 艣cie偶ki w drzewie binarnym, biegn膮ce z korzenia w d贸艂. Zdefiniujmy zwrot na 艣cie偶ce jako zmian臋 w jej kierunku (z prawa na lewo lub odwrotnie). Zygzak to po prostu ci膮g zwrot贸w na pewnej 艣cie偶ce (kt贸ra mo偶e zaczyna膰 si臋 od kierunku w prawo lub w lewo). D艂ugo艣膰 zygzaka to liczba zwrot贸w.
Rozwa偶my nast臋puj膮ce drzewo binarne:
Zaznaczona 艣cie偶ka ma dwa zwroty, kolejno w wierzcho艂kach [15] oraz [30], wi臋c jest to zygzak o d艂ugo艣ci 2, kt贸ry r贸wnocze艣nie jest te偶 najd艂u偶szym zygzakiem w tym drzewie. Twoim zadaniem jest znalezienie d艂ugo艣ci najd艂u偶szego zygzaka zaczynaj膮cego si臋 w korzeniu danego drzewa.
Zygzak sk艂adaj膮cy si臋 tylko z jednej kraw臋dzi lub jednego w臋z艂a ma d艂ugo艣膰 0.
Problem
Napisz funkcj臋:
class Solution { public int solution(Tree T); }
kt贸ra, maj膮c dane niepuste drzewo binarne T zawieraj膮ce N w臋z艂贸w, zwraca d艂ugo艣膰 najd艂u偶szego zygzaka zaczynaj膮cego si臋 w korzeniu.
Na przyk艂ad, maj膮c dane drzewo pokazane na rysunku powy偶ej, funkcja powinna zwr贸ci膰 2, tak jak zosta艂o to wyja艣nione wcze艣niej. Warto艣ci znajduj膮ce si臋 w w臋z艂ach nie s膮 istotne w tym zadaniu.
Szczeg贸艂y techniczne
Drzewo binarne jest dane jako wska藕nikowa struktura danych. Mo偶esz za艂o偶y膰, 偶e nast臋puj膮ce deklaracje zosta艂y zdefiniowane:
class Tree { public int x; public Tree l; public Tree r; }
Puste drzewo jest reprezentowane przez pusty wska藕nik (oznaczany jako null). Niepuste drzewo jest reprezentowane przez wska藕nik do obiektu reprezentuj膮cego korze艅. Atrybut x zawiera liczb臋 ca艂kowit膮 znajduj膮c膮 si臋 w korzeniu, natomiast atrybuty l i r to, odpowiednio, lewe i prawe poddrzewo drzewa binarnego.
Na potrzeby wprowadzania swoich w艂asnych test贸w, mo偶esz opisywa膰 drzewa rekurencyjnie w nast臋puj膮cy spos贸b. Puste drzewo binarne jest oznaczane przez None. Niepuste drzewo binarne jest oznaczane przez (X, L, R), gdzie X to warto艣膰 znajduj膮ca si臋 w korzeniu, a L i R oznaczaj膮, odpowiednio, lewe i prawe poddrzewo. Drzewo przedstawione na rysunku powy偶ej mo偶e by膰 przedstawione jako:
(5, (3, (20, (6, None, None), None), None), (10, (1, None, None), (15, (30, None, (9, None, None)), (8, None, None))))Za艂o偶enia
Za艂o偶enia:
- N to liczba ca艂kowita z przedzia艂u [1..100,000];
- wysoko艣膰 drzewa T (liczba kraw臋dzi na najd艂u偶szej 艣cie偶ce od korzenia do li艣cia) jest z przedzia艂u [0..800].
Copyright 2009–2025 by Codility Limited. All Rights Reserved. Unauthorized copying, publication or disclosure prohibited.
W tym zadaniu rozwa偶amy 艣cie偶ki w drzewie binarnym, biegn膮ce z korzenia w d贸艂. Zdefiniujmy zwrot na 艣cie偶ce jako zmian臋 w jej kierunku (z prawa na lewo lub odwrotnie). Zygzak to po prostu ci膮g zwrot贸w na pewnej 艣cie偶ce (kt贸ra mo偶e zaczyna膰 si臋 od kierunku w prawo lub w lewo). D艂ugo艣膰 zygzaka to liczba zwrot贸w.
Rozwa偶my nast臋puj膮ce drzewo binarne:
Zaznaczona 艣cie偶ka ma dwa zwroty, kolejno w wierzcho艂kach [15] oraz [30], wi臋c jest to zygzak o d艂ugo艣ci 2, kt贸ry r贸wnocze艣nie jest te偶 najd艂u偶szym zygzakiem w tym drzewie. Twoim zadaniem jest znalezienie d艂ugo艣ci najd艂u偶szego zygzaka zaczynaj膮cego si臋 w korzeniu danego drzewa.
Zygzak sk艂adaj膮cy si臋 tylko z jednej kraw臋dzi lub jednego w臋z艂a ma d艂ugo艣膰 0.
Problem
Napisz funkcj臋:
function solution(T);
kt贸ra, maj膮c dane niepuste drzewo binarne T zawieraj膮ce N w臋z艂贸w, zwraca d艂ugo艣膰 najd艂u偶szego zygzaka zaczynaj膮cego si臋 w korzeniu.
Na przyk艂ad, maj膮c dane drzewo pokazane na rysunku powy偶ej, funkcja powinna zwr贸ci膰 2, tak jak zosta艂o to wyja艣nione wcze艣niej. Warto艣ci znajduj膮ce si臋 w w臋z艂ach nie s膮 istotne w tym zadaniu.
Szczeg贸艂y techniczne
Drzewo binarne jest dane jako wska藕nikowa struktura danych. Mo偶esz za艂o偶y膰, 偶e nast臋puj膮ce deklaracje zosta艂y zdefiniowane:
// Tree obj is an Object with attributes // obj.x - type: int // obj.l - type: Tree // obj.r - type: Tree
Puste drzewo jest reprezentowane przez pusty wska藕nik (oznaczany jako null). Niepuste drzewo jest reprezentowane przez wska藕nik do obiektu reprezentuj膮cego korze艅. Atrybut x zawiera liczb臋 ca艂kowit膮 znajduj膮c膮 si臋 w korzeniu, natomiast atrybuty l i r to, odpowiednio, lewe i prawe poddrzewo drzewa binarnego.
Na potrzeby wprowadzania swoich w艂asnych test贸w, mo偶esz opisywa膰 drzewa rekurencyjnie w nast臋puj膮cy spos贸b. Puste drzewo binarne jest oznaczane przez None. Niepuste drzewo binarne jest oznaczane przez (X, L, R), gdzie X to warto艣膰 znajduj膮ca si臋 w korzeniu, a L i R oznaczaj膮, odpowiednio, lewe i prawe poddrzewo. Drzewo przedstawione na rysunku powy偶ej mo偶e by膰 przedstawione jako:
(5, (3, (20, (6, None, None), None), None), (10, (1, None, None), (15, (30, None, (9, None, None)), (8, None, None))))Za艂o偶enia
Za艂o偶enia:
- N to liczba ca艂kowita z przedzia艂u [1..100,000];
- wysoko艣膰 drzewa T (liczba kraw臋dzi na najd艂u偶szej 艣cie偶ce od korzenia do li艣cia) jest z przedzia艂u [0..800].
Copyright 2009–2025 by Codility Limited. All Rights Reserved. Unauthorized copying, publication or disclosure prohibited.
W tym zadaniu rozwa偶amy 艣cie偶ki w drzewie binarnym, biegn膮ce z korzenia w d贸艂. Zdefiniujmy zwrot na 艣cie偶ce jako zmian臋 w jej kierunku (z prawa na lewo lub odwrotnie). Zygzak to po prostu ci膮g zwrot贸w na pewnej 艣cie偶ce (kt贸ra mo偶e zaczyna膰 si臋 od kierunku w prawo lub w lewo). D艂ugo艣膰 zygzaka to liczba zwrot贸w.
Rozwa偶my nast臋puj膮ce drzewo binarne:
Zaznaczona 艣cie偶ka ma dwa zwroty, kolejno w wierzcho艂kach [15] oraz [30], wi臋c jest to zygzak o d艂ugo艣ci 2, kt贸ry r贸wnocze艣nie jest te偶 najd艂u偶szym zygzakiem w tym drzewie. Twoim zadaniem jest znalezienie d艂ugo艣ci najd艂u偶szego zygzaka zaczynaj膮cego si臋 w korzeniu danego drzewa.
Zygzak sk艂adaj膮cy si臋 tylko z jednej kraw臋dzi lub jednego w臋z艂a ma d艂ugo艣膰 0.
Problem
Napisz funkcj臋:
function solution(T)
kt贸ra, maj膮c dane niepuste drzewo binarne T zawieraj膮ce N w臋z艂贸w, zwraca d艂ugo艣膰 najd艂u偶szego zygzaka zaczynaj膮cego si臋 w korzeniu.
Na przyk艂ad, maj膮c dane drzewo pokazane na rysunku powy偶ej, funkcja powinna zwr贸ci膰 2, tak jak zosta艂o to wyja艣nione wcze艣niej. Warto艣ci znajduj膮ce si臋 w w臋z艂ach nie s膮 istotne w tym zadaniu.
Szczeg贸艂y techniczne
Drzewo binarne jest dane jako wska藕nikowa struktura danych. Mo偶esz za艂o偶y膰, 偶e nast臋puj膮ce deklaracje zosta艂y zdefiniowane:
-- Tree obj is an object with attributes -- obj.x - type: int -- obj.l - type: Tree -- obj.r - type: Tree
Puste drzewo jest reprezentowane przez pusty wska藕nik (oznaczany jako nil). Niepuste drzewo jest reprezentowane przez wska藕nik do obiektu reprezentuj膮cego korze艅. Atrybut x zawiera liczb臋 ca艂kowit膮 znajduj膮c膮 si臋 w korzeniu, natomiast atrybuty l i r to, odpowiednio, lewe i prawe poddrzewo drzewa binarnego.
Na potrzeby wprowadzania swoich w艂asnych test贸w, mo偶esz opisywa膰 drzewa rekurencyjnie w nast臋puj膮cy spos贸b. Puste drzewo binarne jest oznaczane przez None. Niepuste drzewo binarne jest oznaczane przez (X, L, R), gdzie X to warto艣膰 znajduj膮ca si臋 w korzeniu, a L i R oznaczaj膮, odpowiednio, lewe i prawe poddrzewo. Drzewo przedstawione na rysunku powy偶ej mo偶e by膰 przedstawione jako:
(5, (3, (20, (6, None, None), None), None), (10, (1, None, None), (15, (30, None, (9, None, None)), (8, None, None))))Za艂o偶enia
Za艂o偶enia:
- N to liczba ca艂kowita z przedzia艂u [1..100,000];
- wysoko艣膰 drzewa T (liczba kraw臋dzi na najd艂u偶szej 艣cie偶ce od korzenia do li艣cia) jest z przedzia艂u [0..800].
Copyright 2009–2025 by Codility Limited. All Rights Reserved. Unauthorized copying, publication or disclosure prohibited.
W tym zadaniu rozwa偶amy 艣cie偶ki w drzewie binarnym, biegn膮ce z korzenia w d贸艂. Zdefiniujmy zwrot na 艣cie偶ce jako zmian臋 w jej kierunku (z prawa na lewo lub odwrotnie). Zygzak to po prostu ci膮g zwrot贸w na pewnej 艣cie偶ce (kt贸ra mo偶e zaczyna膰 si臋 od kierunku w prawo lub w lewo). D艂ugo艣膰 zygzaka to liczba zwrot贸w.
Rozwa偶my nast臋puj膮ce drzewo binarne:
Zaznaczona 艣cie偶ka ma dwa zwroty, kolejno w wierzcho艂kach [15] oraz [30], wi臋c jest to zygzak o d艂ugo艣ci 2, kt贸ry r贸wnocze艣nie jest te偶 najd艂u偶szym zygzakiem w tym drzewie. Twoim zadaniem jest znalezienie d艂ugo艣ci najd艂u偶szego zygzaka zaczynaj膮cego si臋 w korzeniu danego drzewa.
Zygzak sk艂adaj膮cy si臋 tylko z jednej kraw臋dzi lub jednego w臋z艂a ma d艂ugo艣膰 0.
Problem
Napisz funkcj臋:
int solution(Tree * T);
kt贸ra, maj膮c dane niepuste drzewo binarne T zawieraj膮ce N w臋z艂贸w, zwraca d艂ugo艣膰 najd艂u偶szego zygzaka zaczynaj膮cego si臋 w korzeniu.
Na przyk艂ad, maj膮c dane drzewo pokazane na rysunku powy偶ej, funkcja powinna zwr贸ci膰 2, tak jak zosta艂o to wyja艣nione wcze艣niej. Warto艣ci znajduj膮ce si臋 w w臋z艂ach nie s膮 istotne w tym zadaniu.
Szczeg贸艂y techniczne
Drzewo binarne jest dane jako wska藕nikowa struktura danych. Mo偶esz za艂o偶y膰, 偶e nast臋puj膮ce deklaracje zosta艂y zdefiniowane:
@interface Tree : NSObject { @public int x; Tree * l; Tree * r; } @end @implementation Tree @end
Puste drzewo jest reprezentowane przez pusty wska藕nik (oznaczany jako nil). Niepuste drzewo jest reprezentowane przez wska藕nik do obiektu reprezentuj膮cego korze艅. Atrybut x zawiera liczb臋 ca艂kowit膮 znajduj膮c膮 si臋 w korzeniu, natomiast atrybuty l i r to, odpowiednio, lewe i prawe poddrzewo drzewa binarnego.
Na potrzeby wprowadzania swoich w艂asnych test贸w, mo偶esz opisywa膰 drzewa rekurencyjnie w nast臋puj膮cy spos贸b. Puste drzewo binarne jest oznaczane przez None. Niepuste drzewo binarne jest oznaczane przez (X, L, R), gdzie X to warto艣膰 znajduj膮ca si臋 w korzeniu, a L i R oznaczaj膮, odpowiednio, lewe i prawe poddrzewo. Drzewo przedstawione na rysunku powy偶ej mo偶e by膰 przedstawione jako:
(5, (3, (20, (6, None, None), None), None), (10, (1, None, None), (15, (30, None, (9, None, None)), (8, None, None))))Za艂o偶enia
Za艂o偶enia:
- N to liczba ca艂kowita z przedzia艂u [1..100,000];
- wysoko艣膰 drzewa T (liczba kraw臋dzi na najd艂u偶szej 艣cie偶ce od korzenia do li艣cia) jest z przedzia艂u [0..800].
Copyright 2009–2025 by Codility Limited. All Rights Reserved. Unauthorized copying, publication or disclosure prohibited.
W tym zadaniu rozwa偶amy 艣cie偶ki w drzewie binarnym, biegn膮ce z korzenia w d贸艂. Zdefiniujmy zwrot na 艣cie偶ce jako zmian臋 w jej kierunku (z prawa na lewo lub odwrotnie). Zygzak to po prostu ci膮g zwrot贸w na pewnej 艣cie偶ce (kt贸ra mo偶e zaczyna膰 si臋 od kierunku w prawo lub w lewo). D艂ugo艣膰 zygzaka to liczba zwrot贸w.
Rozwa偶my nast臋puj膮ce drzewo binarne:
Zaznaczona 艣cie偶ka ma dwa zwroty, kolejno w wierzcho艂kach [15] oraz [30], wi臋c jest to zygzak o d艂ugo艣ci 2, kt贸ry r贸wnocze艣nie jest te偶 najd艂u偶szym zygzakiem w tym drzewie. Twoim zadaniem jest znalezienie d艂ugo艣ci najd艂u偶szego zygzaka zaczynaj膮cego si臋 w korzeniu danego drzewa.
Zygzak sk艂adaj膮cy si臋 tylko z jednej kraw臋dzi lub jednego w臋z艂a ma d艂ugo艣膰 0.
Problem
Napisz funkcj臋:
function solution(T: Tree): longint;
kt贸ra, maj膮c dane niepuste drzewo binarne T zawieraj膮ce N w臋z艂贸w, zwraca d艂ugo艣膰 najd艂u偶szego zygzaka zaczynaj膮cego si臋 w korzeniu.
Na przyk艂ad, maj膮c dane drzewo pokazane na rysunku powy偶ej, funkcja powinna zwr贸ci膰 2, tak jak zosta艂o to wyja艣nione wcze艣niej. Warto艣ci znajduj膮ce si臋 w w臋z艂ach nie s膮 istotne w tym zadaniu.
Szczeg贸艂y techniczne
Drzewo binarne jest dane jako wska藕nikowa struktura danych. Mo偶esz za艂o偶y膰, 偶e nast臋puj膮ce deklaracje zosta艂y zdefiniowane:
Tree = ^TreeNode; TreeNode = record x : longint; l : Tree; r : Tree; end;
Puste drzewo jest reprezentowane przez pusty wska藕nik (oznaczany jako nil). Niepuste drzewo jest reprezentowane przez wska藕nik do obiektu reprezentuj膮cego korze艅. Atrybut x zawiera liczb臋 ca艂kowit膮 znajduj膮c膮 si臋 w korzeniu, natomiast atrybuty l i r to, odpowiednio, lewe i prawe poddrzewo drzewa binarnego.
Na potrzeby wprowadzania swoich w艂asnych test贸w, mo偶esz opisywa膰 drzewa rekurencyjnie w nast臋puj膮cy spos贸b. Puste drzewo binarne jest oznaczane przez None. Niepuste drzewo binarne jest oznaczane przez (X, L, R), gdzie X to warto艣膰 znajduj膮ca si臋 w korzeniu, a L i R oznaczaj膮, odpowiednio, lewe i prawe poddrzewo. Drzewo przedstawione na rysunku powy偶ej mo偶e by膰 przedstawione jako:
(5, (3, (20, (6, None, None), None), None), (10, (1, None, None), (15, (30, None, (9, None, None)), (8, None, None))))Za艂o偶enia
Za艂o偶enia:
- N to liczba ca艂kowita z przedzia艂u [1..100,000];
- wysoko艣膰 drzewa T (liczba kraw臋dzi na najd艂u偶szej 艣cie偶ce od korzenia do li艣cia) jest z przedzia艂u [0..800].
Copyright 2009–2025 by Codility Limited. All Rights Reserved. Unauthorized copying, publication or disclosure prohibited.
W tym zadaniu rozwa偶amy 艣cie偶ki w drzewie binarnym, biegn膮ce z korzenia w d贸艂. Zdefiniujmy zwrot na 艣cie偶ce jako zmian臋 w jej kierunku (z prawa na lewo lub odwrotnie). Zygzak to po prostu ci膮g zwrot贸w na pewnej 艣cie偶ce (kt贸ra mo偶e zaczyna膰 si臋 od kierunku w prawo lub w lewo). D艂ugo艣膰 zygzaka to liczba zwrot贸w.
Rozwa偶my nast臋puj膮ce drzewo binarne:
Zaznaczona 艣cie偶ka ma dwa zwroty, kolejno w wierzcho艂kach [15] oraz [30], wi臋c jest to zygzak o d艂ugo艣ci 2, kt贸ry r贸wnocze艣nie jest te偶 najd艂u偶szym zygzakiem w tym drzewie. Twoim zadaniem jest znalezienie d艂ugo艣ci najd艂u偶szego zygzaka zaczynaj膮cego si臋 w korzeniu danego drzewa.
Zygzak sk艂adaj膮cy si臋 tylko z jednej kraw臋dzi lub jednego w臋z艂a ma d艂ugo艣膰 0.
Problem
Napisz funkcj臋:
function solution($T);
kt贸ra, maj膮c dane niepuste drzewo binarne T zawieraj膮ce N w臋z艂贸w, zwraca d艂ugo艣膰 najd艂u偶szego zygzaka zaczynaj膮cego si臋 w korzeniu.
Na przyk艂ad, maj膮c dane drzewo pokazane na rysunku powy偶ej, funkcja powinna zwr贸ci膰 2, tak jak zosta艂o to wyja艣nione wcze艣niej. Warto艣ci znajduj膮ce si臋 w w臋z艂ach nie s膮 istotne w tym zadaniu.
Szczeg贸艂y techniczne
Drzewo binarne jest dane jako wska藕nikowa struktura danych. Mo偶esz za艂o偶y膰, 偶e nast臋puj膮ce deklaracje zosta艂y zdefiniowane:
class Tree { var $x = 0; var $l = NULL; var $r = NULL; }
Puste drzewo jest reprezentowane przez pusty wska藕nik (oznaczany jako NULL). Niepuste drzewo jest reprezentowane przez wska藕nik do obiektu reprezentuj膮cego korze艅. Atrybut x zawiera liczb臋 ca艂kowit膮 znajduj膮c膮 si臋 w korzeniu, natomiast atrybuty l i r to, odpowiednio, lewe i prawe poddrzewo drzewa binarnego.
Na potrzeby wprowadzania swoich w艂asnych test贸w, mo偶esz opisywa膰 drzewa rekurencyjnie w nast臋puj膮cy spos贸b. Puste drzewo binarne jest oznaczane przez None. Niepuste drzewo binarne jest oznaczane przez (X, L, R), gdzie X to warto艣膰 znajduj膮ca si臋 w korzeniu, a L i R oznaczaj膮, odpowiednio, lewe i prawe poddrzewo. Drzewo przedstawione na rysunku powy偶ej mo偶e by膰 przedstawione jako:
(5, (3, (20, (6, None, None), None), None), (10, (1, None, None), (15, (30, None, (9, None, None)), (8, None, None))))Za艂o偶enia
Za艂o偶enia:
- N to liczba ca艂kowita z przedzia艂u [1..100,000];
- wysoko艣膰 drzewa T (liczba kraw臋dzi na najd艂u偶szej 艣cie偶ce od korzenia do li艣cia) jest z przedzia艂u [0..800].
Copyright 2009–2025 by Codility Limited. All Rights Reserved. Unauthorized copying, publication or disclosure prohibited.
W tym zadaniu rozwa偶amy 艣cie偶ki w drzewie binarnym, biegn膮ce z korzenia w d贸艂. Zdefiniujmy zwrot na 艣cie偶ce jako zmian臋 w jej kierunku (z prawa na lewo lub odwrotnie). Zygzak to po prostu ci膮g zwrot贸w na pewnej 艣cie偶ce (kt贸ra mo偶e zaczyna膰 si臋 od kierunku w prawo lub w lewo). D艂ugo艣膰 zygzaka to liczba zwrot贸w.
Rozwa偶my nast臋puj膮ce drzewo binarne:
Zaznaczona 艣cie偶ka ma dwa zwroty, kolejno w wierzcho艂kach [15] oraz [30], wi臋c jest to zygzak o d艂ugo艣ci 2, kt贸ry r贸wnocze艣nie jest te偶 najd艂u偶szym zygzakiem w tym drzewie. Twoim zadaniem jest znalezienie d艂ugo艣ci najd艂u偶szego zygzaka zaczynaj膮cego si臋 w korzeniu danego drzewa.
Zygzak sk艂adaj膮cy si臋 tylko z jednej kraw臋dzi lub jednego w臋z艂a ma d艂ugo艣膰 0.
Problem
Napisz funkcj臋:
sub solution { my ($T) = @_; ... }
kt贸ra, maj膮c dane niepuste drzewo binarne T zawieraj膮ce N w臋z艂贸w, zwraca d艂ugo艣膰 najd艂u偶szego zygzaka zaczynaj膮cego si臋 w korzeniu.
Na przyk艂ad, maj膮c dane drzewo pokazane na rysunku powy偶ej, funkcja powinna zwr贸ci膰 2, tak jak zosta艂o to wyja艣nione wcze艣niej. Warto艣ci znajduj膮ce si臋 w w臋z艂ach nie s膮 istotne w tym zadaniu.
Szczeg贸艂y techniczne
Drzewo binarne jest dane jako wska藕nikowa struktura danych. Mo偶esz za艂o偶y膰, 偶e nast臋puj膮ce deklaracje zosta艂y zdefiniowane:
# Tree is a dictionary with keys # 'x' - type: int # 'l' - type: Tree # 'r' - type: Tree
Puste drzewo jest reprezentowane przez pusty wska藕nik (oznaczany jako undef). Niepuste drzewo jest reprezentowane przez wska藕nik do obiektu reprezentuj膮cego korze艅. Atrybut x zawiera liczb臋 ca艂kowit膮 znajduj膮c膮 si臋 w korzeniu, natomiast atrybuty l i r to, odpowiednio, lewe i prawe poddrzewo drzewa binarnego.
Na potrzeby wprowadzania swoich w艂asnych test贸w, mo偶esz opisywa膰 drzewa rekurencyjnie w nast臋puj膮cy spos贸b. Puste drzewo binarne jest oznaczane przez None. Niepuste drzewo binarne jest oznaczane przez (X, L, R), gdzie X to warto艣膰 znajduj膮ca si臋 w korzeniu, a L i R oznaczaj膮, odpowiednio, lewe i prawe poddrzewo. Drzewo przedstawione na rysunku powy偶ej mo偶e by膰 przedstawione jako:
(5, (3, (20, (6, None, None), None), None), (10, (1, None, None), (15, (30, None, (9, None, None)), (8, None, None))))Za艂o偶enia
Za艂o偶enia:
- N to liczba ca艂kowita z przedzia艂u [1..100,000];
- wysoko艣膰 drzewa T (liczba kraw臋dzi na najd艂u偶szej 艣cie偶ce od korzenia do li艣cia) jest z przedzia艂u [0..800].
Copyright 2009–2025 by Codility Limited. All Rights Reserved. Unauthorized copying, publication or disclosure prohibited.
W tym zadaniu rozwa偶amy 艣cie偶ki w drzewie binarnym, biegn膮ce z korzenia w d贸艂. Zdefiniujmy zwrot na 艣cie偶ce jako zmian臋 w jej kierunku (z prawa na lewo lub odwrotnie). Zygzak to po prostu ci膮g zwrot贸w na pewnej 艣cie偶ce (kt贸ra mo偶e zaczyna膰 si臋 od kierunku w prawo lub w lewo). D艂ugo艣膰 zygzaka to liczba zwrot贸w.
Rozwa偶my nast臋puj膮ce drzewo binarne:
Zaznaczona 艣cie偶ka ma dwa zwroty, kolejno w wierzcho艂kach [15] oraz [30], wi臋c jest to zygzak o d艂ugo艣ci 2, kt贸ry r贸wnocze艣nie jest te偶 najd艂u偶szym zygzakiem w tym drzewie. Twoim zadaniem jest znalezienie d艂ugo艣ci najd艂u偶szego zygzaka zaczynaj膮cego si臋 w korzeniu danego drzewa.
Zygzak sk艂adaj膮cy si臋 tylko z jednej kraw臋dzi lub jednego w臋z艂a ma d艂ugo艣膰 0.
Problem
Napisz funkcj臋:
def solution(T)
kt贸ra, maj膮c dane niepuste drzewo binarne T zawieraj膮ce N w臋z艂贸w, zwraca d艂ugo艣膰 najd艂u偶szego zygzaka zaczynaj膮cego si臋 w korzeniu.
Na przyk艂ad, maj膮c dane drzewo pokazane na rysunku powy偶ej, funkcja powinna zwr贸ci膰 2, tak jak zosta艂o to wyja艣nione wcze艣niej. Warto艣ci znajduj膮ce si臋 w w臋z艂ach nie s膮 istotne w tym zadaniu.
Szczeg贸艂y techniczne
Drzewo binarne jest dane jako wska藕nikowa struktura danych. Mo偶esz za艂o偶y膰, 偶e nast臋puj膮ce deklaracje zosta艂y zdefiniowane:
from dataclasses import dataclass, field @dataclass class Tree: x: int = 0 l: "Tree" = None r: "Tree" = None
Puste drzewo jest reprezentowane przez pusty wska藕nik (oznaczany jako None). Niepuste drzewo jest reprezentowane przez wska藕nik do obiektu reprezentuj膮cego korze艅. Atrybut x zawiera liczb臋 ca艂kowit膮 znajduj膮c膮 si臋 w korzeniu, natomiast atrybuty l i r to, odpowiednio, lewe i prawe poddrzewo drzewa binarnego.
Na potrzeby wprowadzania swoich w艂asnych test贸w, mo偶esz opisywa膰 drzewa rekurencyjnie w nast臋puj膮cy spos贸b. Puste drzewo binarne jest oznaczane przez None. Niepuste drzewo binarne jest oznaczane przez (X, L, R), gdzie X to warto艣膰 znajduj膮ca si臋 w korzeniu, a L i R oznaczaj膮, odpowiednio, lewe i prawe poddrzewo. Drzewo przedstawione na rysunku powy偶ej mo偶e by膰 przedstawione jako:
(5, (3, (20, (6, None, None), None), None), (10, (1, None, None), (15, (30, None, (9, None, None)), (8, None, None))))Za艂o偶enia
Za艂o偶enia:
- N to liczba ca艂kowita z przedzia艂u [1..100,000];
- wysoko艣膰 drzewa T (liczba kraw臋dzi na najd艂u偶szej 艣cie偶ce od korzenia do li艣cia) jest z przedzia艂u [0..800].
Copyright 2009–2025 by Codility Limited. All Rights Reserved. Unauthorized copying, publication or disclosure prohibited.
W tym zadaniu rozwa偶amy 艣cie偶ki w drzewie binarnym, biegn膮ce z korzenia w d贸艂. Zdefiniujmy zwrot na 艣cie偶ce jako zmian臋 w jej kierunku (z prawa na lewo lub odwrotnie). Zygzak to po prostu ci膮g zwrot贸w na pewnej 艣cie偶ce (kt贸ra mo偶e zaczyna膰 si臋 od kierunku w prawo lub w lewo). D艂ugo艣膰 zygzaka to liczba zwrot贸w.
Rozwa偶my nast臋puj膮ce drzewo binarne:
Zaznaczona 艣cie偶ka ma dwa zwroty, kolejno w wierzcho艂kach [15] oraz [30], wi臋c jest to zygzak o d艂ugo艣ci 2, kt贸ry r贸wnocze艣nie jest te偶 najd艂u偶szym zygzakiem w tym drzewie. Twoim zadaniem jest znalezienie d艂ugo艣ci najd艂u偶szego zygzaka zaczynaj膮cego si臋 w korzeniu danego drzewa.
Zygzak sk艂adaj膮cy si臋 tylko z jednej kraw臋dzi lub jednego w臋z艂a ma d艂ugo艣膰 0.
Problem
Napisz funkcj臋:
def solution(t)
kt贸ra, maj膮c dane niepuste drzewo binarne T zawieraj膮ce N w臋z艂贸w, zwraca d艂ugo艣膰 najd艂u偶szego zygzaka zaczynaj膮cego si臋 w korzeniu.
Na przyk艂ad, maj膮c dane drzewo pokazane na rysunku powy偶ej, funkcja powinna zwr贸ci膰 2, tak jak zosta艂o to wyja艣nione wcze艣niej. Warto艣ci znajduj膮ce si臋 w w臋z艂ach nie s膮 istotne w tym zadaniu.
Szczeg贸艂y techniczne
Drzewo binarne jest dane jako wska藕nikowa struktura danych. Mo偶esz za艂o偶y膰, 偶e nast臋puj膮ce deklaracje zosta艂y zdefiniowane:
class Tree attr_accessor :x, :l, :r end
Puste drzewo jest reprezentowane przez pusty wska藕nik (oznaczany jako nil). Niepuste drzewo jest reprezentowane przez wska藕nik do obiektu reprezentuj膮cego korze艅. Atrybut x zawiera liczb臋 ca艂kowit膮 znajduj膮c膮 si臋 w korzeniu, natomiast atrybuty l i r to, odpowiednio, lewe i prawe poddrzewo drzewa binarnego.
Na potrzeby wprowadzania swoich w艂asnych test贸w, mo偶esz opisywa膰 drzewa rekurencyjnie w nast臋puj膮cy spos贸b. Puste drzewo binarne jest oznaczane przez None. Niepuste drzewo binarne jest oznaczane przez (X, L, R), gdzie X to warto艣膰 znajduj膮ca si臋 w korzeniu, a L i R oznaczaj膮, odpowiednio, lewe i prawe poddrzewo. Drzewo przedstawione na rysunku powy偶ej mo偶e by膰 przedstawione jako:
(5, (3, (20, (6, None, None), None), None), (10, (1, None, None), (15, (30, None, (9, None, None)), (8, None, None))))Za艂o偶enia
Za艂o偶enia:
- N to liczba ca艂kowita z przedzia艂u [1..100,000];
- wysoko艣膰 drzewa T (liczba kraw臋dzi na najd艂u偶szej 艣cie偶ce od korzenia do li艣cia) jest z przedzia艂u [0..800].
Copyright 2009–2025 by Codility Limited. All Rights Reserved. Unauthorized copying, publication or disclosure prohibited.
W tym zadaniu rozwa偶amy 艣cie偶ki w drzewie binarnym, biegn膮ce z korzenia w d贸艂. Zdefiniujmy zwrot na 艣cie偶ce jako zmian臋 w jej kierunku (z prawa na lewo lub odwrotnie). Zygzak to po prostu ci膮g zwrot贸w na pewnej 艣cie偶ce (kt贸ra mo偶e zaczyna膰 si臋 od kierunku w prawo lub w lewo). D艂ugo艣膰 zygzaka to liczba zwrot贸w.
Rozwa偶my nast臋puj膮ce drzewo binarne:
Zaznaczona 艣cie偶ka ma dwa zwroty, kolejno w wierzcho艂kach [15] oraz [30], wi臋c jest to zygzak o d艂ugo艣ci 2, kt贸ry r贸wnocze艣nie jest te偶 najd艂u偶szym zygzakiem w tym drzewie. Twoim zadaniem jest znalezienie d艂ugo艣ci najd艂u偶szego zygzaka zaczynaj膮cego si臋 w korzeniu danego drzewa.
Zygzak sk艂adaj膮cy si臋 tylko z jednej kraw臋dzi lub jednego w臋z艂a ma d艂ugo艣膰 0.
Problem
Napisz funkcj臋:
object Solution { def solution(t: Tree): Int }
kt贸ra, maj膮c dane niepuste drzewo binarne T zawieraj膮ce N w臋z艂贸w, zwraca d艂ugo艣膰 najd艂u偶szego zygzaka zaczynaj膮cego si臋 w korzeniu.
Na przyk艂ad, maj膮c dane drzewo pokazane na rysunku powy偶ej, funkcja powinna zwr贸ci膰 2, tak jak zosta艂o to wyja艣nione wcze艣niej. Warto艣ci znajduj膮ce si臋 w w臋z艂ach nie s膮 istotne w tym zadaniu.
Szczeg贸艂y techniczne
Drzewo binarne jest dane jako wska藕nikowa struktura danych. Mo偶esz za艂o偶y膰, 偶e nast臋puj膮ce deklaracje zosta艂y zdefiniowane:
class Tree(var x: Int, var l: Tree, var r: Tree)
Puste drzewo jest reprezentowane przez pusty wska藕nik (oznaczany jako null). Niepuste drzewo jest reprezentowane przez wska藕nik do obiektu reprezentuj膮cego korze艅. Atrybut x zawiera liczb臋 ca艂kowit膮 znajduj膮c膮 si臋 w korzeniu, natomiast atrybuty l i r to, odpowiednio, lewe i prawe poddrzewo drzewa binarnego.
Na potrzeby wprowadzania swoich w艂asnych test贸w, mo偶esz opisywa膰 drzewa rekurencyjnie w nast臋puj膮cy spos贸b. Puste drzewo binarne jest oznaczane przez None. Niepuste drzewo binarne jest oznaczane przez (X, L, R), gdzie X to warto艣膰 znajduj膮ca si臋 w korzeniu, a L i R oznaczaj膮, odpowiednio, lewe i prawe poddrzewo. Drzewo przedstawione na rysunku powy偶ej mo偶e by膰 przedstawione jako:
(5, (3, (20, (6, None, None), None), None), (10, (1, None, None), (15, (30, None, (9, None, None)), (8, None, None))))Za艂o偶enia
Za艂o偶enia:
- N to liczba ca艂kowita z przedzia艂u [1..100,000];
- wysoko艣膰 drzewa T (liczba kraw臋dzi na najd艂u偶szej 艣cie偶ce od korzenia do li艣cia) jest z przedzia艂u [0..800].
Copyright 2009–2025 by Codility Limited. All Rights Reserved. Unauthorized copying, publication or disclosure prohibited.
W tym zadaniu rozwa偶amy 艣cie偶ki w drzewie binarnym, biegn膮ce z korzenia w d贸艂. Zdefiniujmy zwrot na 艣cie偶ce jako zmian臋 w jej kierunku (z prawa na lewo lub odwrotnie). Zygzak to po prostu ci膮g zwrot贸w na pewnej 艣cie偶ce (kt贸ra mo偶e zaczyna膰 si臋 od kierunku w prawo lub w lewo). D艂ugo艣膰 zygzaka to liczba zwrot贸w.
Rozwa偶my nast臋puj膮ce drzewo binarne:
Zaznaczona 艣cie偶ka ma dwa zwroty, kolejno w wierzcho艂kach [15] oraz [30], wi臋c jest to zygzak o d艂ugo艣ci 2, kt贸ry r贸wnocze艣nie jest te偶 najd艂u偶szym zygzakiem w tym drzewie. Twoim zadaniem jest znalezienie d艂ugo艣ci najd艂u偶szego zygzaka zaczynaj膮cego si臋 w korzeniu danego drzewa.
Zygzak sk艂adaj膮cy si臋 tylko z jednej kraw臋dzi lub jednego w臋z艂a ma d艂ugo艣膰 0.
Problem
Napisz funkcj臋:
public func solution(_ T : Tree?) -> Int
kt贸ra, maj膮c dane niepuste drzewo binarne T zawieraj膮ce N w臋z艂贸w, zwraca d艂ugo艣膰 najd艂u偶szego zygzaka zaczynaj膮cego si臋 w korzeniu.
Na przyk艂ad, maj膮c dane drzewo pokazane na rysunku powy偶ej, funkcja powinna zwr贸ci膰 2, tak jak zosta艂o to wyja艣nione wcze艣niej. Warto艣ci znajduj膮ce si臋 w w臋z艂ach nie s膮 istotne w tym zadaniu.
Szczeg贸艂y techniczne
Drzewo binarne jest dane jako wska藕nikowa struktura danych. Mo偶esz za艂o偶y膰, 偶e nast臋puj膮ce deklaracje zosta艂y zdefiniowane:
public class Tree { public var x : Int = 0 public var l : Tree? public var r : Tree? public init() {} }
Puste drzewo jest reprezentowane przez pusty wska藕nik (oznaczany jako nil). Niepuste drzewo jest reprezentowane przez wska藕nik do obiektu reprezentuj膮cego korze艅. Atrybut x zawiera liczb臋 ca艂kowit膮 znajduj膮c膮 si臋 w korzeniu, natomiast atrybuty l i r to, odpowiednio, lewe i prawe poddrzewo drzewa binarnego.
Na potrzeby wprowadzania swoich w艂asnych test贸w, mo偶esz opisywa膰 drzewa rekurencyjnie w nast臋puj膮cy spos贸b. Puste drzewo binarne jest oznaczane przez None. Niepuste drzewo binarne jest oznaczane przez (X, L, R), gdzie X to warto艣膰 znajduj膮ca si臋 w korzeniu, a L i R oznaczaj膮, odpowiednio, lewe i prawe poddrzewo. Drzewo przedstawione na rysunku powy偶ej mo偶e by膰 przedstawione jako:
(5, (3, (20, (6, None, None), None), None), (10, (1, None, None), (15, (30, None, (9, None, None)), (8, None, None))))Za艂o偶enia
Za艂o偶enia:
- N to liczba ca艂kowita z przedzia艂u [1..100,000];
- wysoko艣膰 drzewa T (liczba kraw臋dzi na najd艂u偶szej 艣cie偶ce od korzenia do li艣cia) jest z przedzia艂u [0..800].
Copyright 2009–2025 by Codility Limited. All Rights Reserved. Unauthorized copying, publication or disclosure prohibited.
W tym zadaniu rozwa偶amy 艣cie偶ki w drzewie binarnym, biegn膮ce z korzenia w d贸艂. Zdefiniujmy zwrot na 艣cie偶ce jako zmian臋 w jej kierunku (z prawa na lewo lub odwrotnie). Zygzak to po prostu ci膮g zwrot贸w na pewnej 艣cie偶ce (kt贸ra mo偶e zaczyna膰 si臋 od kierunku w prawo lub w lewo). D艂ugo艣膰 zygzaka to liczba zwrot贸w.
Rozwa偶my nast臋puj膮ce drzewo binarne:
Zaznaczona 艣cie偶ka ma dwa zwroty, kolejno w wierzcho艂kach [15] oraz [30], wi臋c jest to zygzak o d艂ugo艣ci 2, kt贸ry r贸wnocze艣nie jest te偶 najd艂u偶szym zygzakiem w tym drzewie. Twoim zadaniem jest znalezienie d艂ugo艣ci najd艂u偶szego zygzaka zaczynaj膮cego si臋 w korzeniu danego drzewa.
Zygzak sk艂adaj膮cy si臋 tylko z jednej kraw臋dzi lub jednego w臋z艂a ma d艂ugo艣膰 0.
Problem
Napisz funkcj臋:
function solution(T: Tree): number;
kt贸ra, maj膮c dane niepuste drzewo binarne T zawieraj膮ce N w臋z艂贸w, zwraca d艂ugo艣膰 najd艂u偶szego zygzaka zaczynaj膮cego si臋 w korzeniu.
Na przyk艂ad, maj膮c dane drzewo pokazane na rysunku powy偶ej, funkcja powinna zwr贸ci膰 2, tak jak zosta艂o to wyja艣nione wcze艣niej. Warto艣ci znajduj膮ce si臋 w w臋z艂ach nie s膮 istotne w tym zadaniu.
Szczeg贸艂y techniczne
Drzewo binarne jest dane jako wska藕nikowa struktura danych. Mo偶esz za艂o偶y膰, 偶e nast臋puj膮ce deklaracje zosta艂y zdefiniowane:
class Tree { x: number; l: Tree; r: Tree; constructor(x: number = 0, l: Tree = null, r: Tree = null) { this.x = x; this.l = l; this.r = r; } }
Puste drzewo jest reprezentowane przez pusty wska藕nik (oznaczany jako null). Niepuste drzewo jest reprezentowane przez wska藕nik do obiektu reprezentuj膮cego korze艅. Atrybut x zawiera liczb臋 ca艂kowit膮 znajduj膮c膮 si臋 w korzeniu, natomiast atrybuty l i r to, odpowiednio, lewe i prawe poddrzewo drzewa binarnego.
Na potrzeby wprowadzania swoich w艂asnych test贸w, mo偶esz opisywa膰 drzewa rekurencyjnie w nast臋puj膮cy spos贸b. Puste drzewo binarne jest oznaczane przez None. Niepuste drzewo binarne jest oznaczane przez (X, L, R), gdzie X to warto艣膰 znajduj膮ca si臋 w korzeniu, a L i R oznaczaj膮, odpowiednio, lewe i prawe poddrzewo. Drzewo przedstawione na rysunku powy偶ej mo偶e by膰 przedstawione jako:
(5, (3, (20, (6, None, None), None), None), (10, (1, None, None), (15, (30, None, (9, None, None)), (8, None, None))))Za艂o偶enia
Za艂o偶enia:
- N to liczba ca艂kowita z przedzia艂u [1..100,000];
- wysoko艣膰 drzewa T (liczba kraw臋dzi na najd艂u偶szej 艣cie偶ce od korzenia do li艣cia) jest z przedzia艂u [0..800].
Copyright 2009–2025 by Codility Limited. All Rights Reserved. Unauthorized copying, publication or disclosure prohibited.
W tym zadaniu rozwa偶amy 艣cie偶ki w drzewie binarnym, biegn膮ce z korzenia w d贸艂. Zdefiniujmy zwrot na 艣cie偶ce jako zmian臋 w jej kierunku (z prawa na lewo lub odwrotnie). Zygzak to po prostu ci膮g zwrot贸w na pewnej 艣cie偶ce (kt贸ra mo偶e zaczyna膰 si臋 od kierunku w prawo lub w lewo). D艂ugo艣膰 zygzaka to liczba zwrot贸w.
Rozwa偶my nast臋puj膮ce drzewo binarne:
Zaznaczona 艣cie偶ka ma dwa zwroty, kolejno w wierzcho艂kach [15] oraz [30], wi臋c jest to zygzak o d艂ugo艣ci 2, kt贸ry r贸wnocze艣nie jest te偶 najd艂u偶szym zygzakiem w tym drzewie. Twoim zadaniem jest znalezienie d艂ugo艣ci najd艂u偶szego zygzaka zaczynaj膮cego si臋 w korzeniu danego drzewa.
Zygzak sk艂adaj膮cy si臋 tylko z jednej kraw臋dzi lub jednego w臋z艂a ma d艂ugo艣膰 0.
Problem
Napisz funkcj臋:
Private Function solution(T As Tree) As Integer
kt贸ra, maj膮c dane niepuste drzewo binarne T zawieraj膮ce N w臋z艂贸w, zwraca d艂ugo艣膰 najd艂u偶szego zygzaka zaczynaj膮cego si臋 w korzeniu.
Na przyk艂ad, maj膮c dane drzewo pokazane na rysunku powy偶ej, funkcja powinna zwr贸ci膰 2, tak jak zosta艂o to wyja艣nione wcze艣niej. Warto艣ci znajduj膮ce si臋 w w臋z艂ach nie s膮 istotne w tym zadaniu.
Szczeg贸艂y techniczne
Drzewo binarne jest dane jako wska藕nikowa struktura danych. Mo偶esz za艂o偶y膰, 偶e nast臋puj膮ce deklaracje zosta艂y zdefiniowane:
Class Tree Public x As Integer Public l As Tree Public r As Tree End Class
Puste drzewo jest reprezentowane przez pusty wska藕nik (oznaczany jako Nothing). Niepuste drzewo jest reprezentowane przez wska藕nik do obiektu reprezentuj膮cego korze艅. Atrybut x zawiera liczb臋 ca艂kowit膮 znajduj膮c膮 si臋 w korzeniu, natomiast atrybuty l i r to, odpowiednio, lewe i prawe poddrzewo drzewa binarnego.
Na potrzeby wprowadzania swoich w艂asnych test贸w, mo偶esz opisywa膰 drzewa rekurencyjnie w nast臋puj膮cy spos贸b. Puste drzewo binarne jest oznaczane przez None. Niepuste drzewo binarne jest oznaczane przez (X, L, R), gdzie X to warto艣膰 znajduj膮ca si臋 w korzeniu, a L i R oznaczaj膮, odpowiednio, lewe i prawe poddrzewo. Drzewo przedstawione na rysunku powy偶ej mo偶e by膰 przedstawione jako:
(5, (3, (20, (6, None, None), None), None), (10, (1, None, None), (15, (30, None, (9, None, None)), (8, None, None))))Za艂o偶enia
Za艂o偶enia:
- N to liczba ca艂kowita z przedzia艂u [1..100,000];
- wysoko艣膰 drzewa T (liczba kraw臋dzi na najd艂u偶szej 艣cie偶ce od korzenia do li艣cia) jest z przedzia艂u [0..800].
Copyright 2009–2025 by Codility Limited. All Rights Reserved. Unauthorized copying, publication or disclosure prohibited.
