1372. Longest ZigZag Path in a Binary Tree Medium

1/**
2 * [1372] Longest ZigZag Path in a Binary Tree
3 *
4 * You are given the root of a binary tree.
5 * A ZigZag path for a binary tree is defined as follow:
6 * 
7 * 	Choose any node in the binary tree and a direction (right or left).
8 * 	If the current direction is right, move to the right child of the current node; otherwise, move to the left child.
9 * 	Change the direction from right to left or from left to right.
10 * 	Repeat the second and third steps until you can't move in the tree.
11 * 
12 * Zigzag length is defined as the number of nodes visited - 1. (A single node has a length of 0).
13 * Return the longest ZigZag path contained in that tree.
14 *  
15 * Example 1:
16 * <img alt="" src="https://assets.leetcode.com/uploads/2020/01/22/sample_1_1702.png" style="width: 221px; height: 383px;" />
17 * Input: root = [1,null,1,1,1,null,null,1,1,null,1,null,null,null,1,null,1]
18 * Output: 3
19 * Explanation: Longest ZigZag path in blue nodes (right -> left -> right).
20 * 
21 * Example 2:
22 * <img alt="" src="https://assets.leetcode.com/uploads/2020/01/22/sample_2_1702.png" style="width: 157px; height: 329px;" />
23 * Input: root = [1,1,1,null,1,null,null,1,1,null,1]
24 * Output: 4
25 * Explanation: Longest ZigZag path in blue nodes (left -> right -> left -> right).
26 * 
27 * Example 3:
28 * 
29 * Input: root = [1]
30 * Output: 0
31 * 
32 *  
33 * Constraints:
34 * 
35 * 	The number of nodes in the tree is in the range [1, 5 * 10^4].
36 * 	1 <= Node.val <= 100
37 * 
38 */
39pub struct Solution {}
40use crate::util::tree::{TreeNode, to_tree};
41
42// problem: https://leetcode.com/problems/longest-zigzag-path-in-a-binary-tree/
43// discuss: https://leetcode.com/problems/longest-zigzag-path-in-a-binary-tree/discuss/?currentPage=1&orderBy=most_votes&query=
44
45// submission codes start here
46
47// Definition for a binary tree node.
48// #[derive(Debug, PartialEq, Eq)]
49// pub struct TreeNode {
50//   pub val: i32,
51//   pub left: Option<Rc<RefCell<TreeNode>>>,
52//   pub right: Option<Rc<RefCell<TreeNode>>>,
53// }
54// 
55// impl TreeNode {
56//   #[inline]
57//   pub fn new(val: i32) -> Self {
58//     TreeNode {
59//       val,
60//       left: None,
61//       right: None
62//     }
63//   }
64// }
65use std::rc::Rc;
66use std::cell::RefCell;
67impl Solution {
68    pub fn longest_zig_zag(root: Option<Rc<RefCell<TreeNode>>>) -> i32 {
69        0
70    }
71}
72
73// submission codes end
74
75#[cfg(test)]
76mod tests {
77    use super::*;
78
79    #[test]
80    fn test_1372() {
81    }
82}
83