1372. Longest ZigZag Path in a Binary Tree

leetcode medium

#csharp#graph#leetcode#math#medium#recursion#string#tree#two-pointers

Task

Вам дан корень бинарного дерева.

Зигзагообразный путь для бинарного дерева определяется следующим образом:

Выберите любой узел в бинарном дереве и направление (вправо или влево).

Если текущее направление вправо, перейдите к правому дочернему узлу текущего узла; иначе перейдите к левому дочернему узлу.

Измените направление с вправо на влево или с влево на вправо.

Повторяйте второй и третий шаги, пока не сможете двигаться по дереву.

Длина зигзагообразного пути определяется как количество посещенных узлов минус 1 (один узел имеет длину 0).

Верните длину самого длинного зигзагообразного пути, содержащегося в этом дереве.

Пример

Input: s = "rat"

Output: "art"

Explanation: The word "rat" becomes "art" after re-ordering it with the mentioned algorithm.

C# solution

matched/original

public class TreeNode {
    public int val;
    public TreeNode left;
    public TreeNode right;
    public TreeNode(int x) { val = x; }
}
public class Solution {
    private int maxLength = 0;
    public int LongestZigZag(TreeNode root) {
        Dfs(root, true, 0);
        Dfs(root, false, 0);
        return maxLength;
    }
    private void Dfs(TreeNode node, bool isLeft, int length) {
        if (node == null) return;
        maxLength = Math.Max(maxLength, length);
        if (isLeft) {
            Dfs(node.left, false, length + 1);
            Dfs(node.right, true, 1);
        } else {
            Dfs(node.right, true, length + 1);
            Dfs(node.left, false, 1);
        }
    }
}

C++ solution

auto-draft, review before submit

#include <bits/stdc++.h>
using namespace std;

// Auto-generated C++ draft from the C# solution. Review containers, LINQ and helper types before submit.
public class TreeNode {
    public int val;
    public TreeNode left;
    public TreeNode right;
    public TreeNode(int x) { val = x; }
}
class Solution {
public:
    private int maxLength = 0;
    public int LongestZigZag(TreeNode root) {
        Dfs(root, true, 0);
        Dfs(root, false, 0);
        return maxLength;
    }
    private void Dfs(TreeNode node, bool isLeft, int length) {
        if (node == null) return;
        maxLength = max(maxLength, length);
        if (isLeft) {
            Dfs(node.left, false, length + 1);
            Dfs(node.right, true, 1);
        } else {
            Dfs(node.right, true, length + 1);
            Dfs(node.left, false, 1);
        }
    }
}

Java solution

matched/original

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int x) { val = x; }
}

public class Solution {
    private int maxLength = 0;

    public int longestZigZag(TreeNode root) {
        dfs(root, true, 0);
        dfs(root, false, 0);
        return maxLength;
    }

    private void dfs(TreeNode node, boolean isLeft, int length) {
        if (node == null) {
            return;
        }
        maxLength = Math.max(maxLength, length);
        if (isLeft) {
            dfs(node.left, false, length + 1);
            dfs(node.right, true, 1);
        } else {
            dfs(node.right, true, length + 1);
            dfs(node.left, false, 1);
        }
    }
}

JavaScript solution

matched/original

var longestZigZag = function(root) {
    let maxLength = 0;

    const dfs = (node, isLeft, length) => {
        if (!node) return;
        maxLength = Math.max(maxLength, length);
        if (isLeft) {
            dfs(node.left, false, length + 1);
            dfs(node.right, true, 1);
        } else {
            dfs(node.right, true, length + 1);
            dfs(node.left, false, 1);
        }
    };

    dfs(root, true, 0);
    dfs(root, false, 0);

    return maxLength;
};

Python solution

matched/original

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:
        self.max_length = 0
        
        def dfs(node, is_left, length):
            if not node:
                return
            self.max_length = max(self.max_length, length)
            if is_left:
                dfs(node.left, False, length + 1)
                dfs(node.right, True, 1)
            else:
                dfs(node.right, True, length + 1)
                dfs(node.left, False, 1)
        
        dfs(root, True, 0)
        dfs(root, False, 0)
        
        return self.max_length

Go solution

matched/original

type TreeNode struct {
    Val   int
    Left  *TreeNode
    Right *TreeNode
}

func longestZigZag(root *TreeNode) int {
    maxLength := 0

    var dfs func(node *TreeNode, isLeft bool, length int)
    dfs = func(node *TreeNode, isLeft bool, length int) {
        if node == nil {
            return
        }
        if length > maxLength {
            maxLength = length
        }
        if isLeft {
            dfs(node.Left, false, length+1)
            dfs(node.Right, true, 1)
        } else {
            dfs(node.Right, true, length+1)
            dfs(node.Left, false, 1)
        }
    }

    dfs(root, true, 0)
    dfs(root, false, 0)

    return maxLength
}

Explanation

Algorithm

Рекурсивная функция DFS:

Создайте рекурсивную функцию dfs, которая будет выполнять обход дерева и отслеживать текущую длину зигзагообразного пути и направление движения (влево или вправо).

Обновление максимальной длины пути:

При каждом вызове рекурсивной функции обновляйте максимальную длину зигзагообразного пути, если текущая длина больше текущего максимума.

Рекурсивный вызов для левого и правого дочерних узлов:

Рекурсивно вызывайте функцию dfs для левого и правого дочерних узлов с обновленными параметрами длины и направления.

😎