TreeLongestZigZag coding task - Practice Coding

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].

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].

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].

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].

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].

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].

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].

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].

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].

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].

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].

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].

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].

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].

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].

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].

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].

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].

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].

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].

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].

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].

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].

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].

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].

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].

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].

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].

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].

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].

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].

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].

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].

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].

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].

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].

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].

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].

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].

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].