Tree
Depth-First Search
Dynamic Programming
Binary Tree
Description
You are given the root
of a binary tree.
A ZigZag path for a binary tree is defined as follow:
Choose any node in the binary tree and a direction (right or left).
If the current direction is right, move to the right child of the current node; otherwise, move to the left child.
Change the direction from right to left or from left to right.
Repeat the second and third steps until you can't move in the tree.
Zigzag length is defined as the number of nodes visited - 1. (A single node has a length of 0).
Return the longest ZigZag path contained in that tree .
Example 1:
Input: root = [1,null,1,1,1,null,null,1,1,null,1,null,null,null,1]
Output: 3
Explanation: Longest ZigZag path in blue nodes (right -> left -> right).
Example 2:
Input: root = [1,1,1,null,1,null,null,1,1,null,1]
Output: 4
Explanation: Longest ZigZag path in blue nodes (left -> right -> left -> right).
Example 3:
Input: root = [1]
Output: 0
Constraints:
The number of nodes in the tree is in the range [1, 5 * 104 ]
.
1 <= Node.val <= 100
Solutions
Solution 1
Python3 Java C++ Go
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19 # Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution :
def longestZigZag ( self , root : TreeNode ) -> int :
def dfs ( root , l , r ):
if root is None :
return
nonlocal ans
ans = max ( ans , l , r )
dfs ( root . left , r + 1 , 0 )
dfs ( root . right , 0 , l + 1 )
ans = 0
dfs ( root , 0 , 0 )
return ans
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32 /**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
private int ans ;
public int longestZigZag ( TreeNode root ) {
dfs ( root , 0 , 0 );
return ans ;
}
private void dfs ( TreeNode root , int l , int r ) {
if ( root == null ) {
return ;
}
ans = Math . max ( ans , Math . max ( l , r ));
dfs ( root . left , r + 1 , 0 );
dfs ( root . right , 0 , l + 1 );
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27 /**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public :
int ans = 0 ;
int longestZigZag ( TreeNode * root ) {
dfs ( root , 0 , 0 );
return ans ;
}
void dfs ( TreeNode * root , int l , int r ) {
if ( ! root ) return ;
ans = max ( ans , max ( l , r ));
dfs ( root -> left , r + 1 , 0 );
dfs ( root -> right , 0 , l + 1 );
}
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22 /**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
func longestZigZag ( root * TreeNode ) int {
ans := 0
var dfs func ( root * TreeNode , l , r int )
dfs = func ( root * TreeNode , l , r int ) {
if root == nil {
return
}
ans = max ( ans , max ( l , r ))
dfs ( root . Left , r + 1 , 0 )
dfs ( root . Right , 0 , l + 1 )
}
dfs ( root , 0 , 0 )
return ans
}
GitHub