# -*- coding: utf-8 -*-

"""
@Author: xiezizhe
@Date: 30/8/2020 上午12:56
"""

from collections import defaultdict


class Solution:
    def longestZigZag(self, root: TreeNode) -> int:

        levels = [root]
        ret = 0
        dp_r = defaultdict(int)
        dp_l = defaultdict(int)
        while levels:

            nxt = []

            for p in levels:
                if p.left:
                    nxt.append(p.left)
                    dp_l[p.left] = dp_r[p] + 1
                    ret = max(ret, dp_l[p.left])

                if p.right:
                    nxt.append(p.right)
                    dp_r[p.right] = dp_l[p] + 1
                    ret = max(ret, dp_r[p.right])

            levels = nxt

        return ret
48242e026615ad992774d5969aee3b7ba9c37740
<mask token>

<mask token>


class Solution:
    <mask token>

<mask token>


class Solution:

    def longestZigZag(self, root: TreeNode) ->int:
        levels = [root]
        ret = 0
        dp_r = defaultdict(int)
        dp_l = defaultdict(int)
        while levels:
            nxt = []
            for p in levels:
                if p.left:
                    nxt.append(p.left)
                    dp_l[p.left] = dp_r[p] + 1
                    ret = max(ret, dp_l[p.left])
                if p.right:
                    nxt.append(p.right)
                    dp_r[p.right] = dp_l[p] + 1
                    ret = max(ret, dp_r[p.right])
            levels = nxt
        return ret

<mask token>
from collections import defaultdict


class Solution:

    def longestZigZag(self, root: TreeNode) ->int:
        levels = [root]
        ret = 0
        dp_r = defaultdict(int)
        dp_l = defaultdict(int)
        while levels:
            nxt = []
            for p in levels:
                if p.left:
                    nxt.append(p.left)
                    dp_l[p.left] = dp_r[p] + 1
                    ret = max(ret, dp_l[p.left])
                if p.right:
                    nxt.append(p.right)
                    dp_r[p.right] = dp_l[p] + 1
                    ret = max(ret, dp_r[p.right])
            levels = nxt
        return ret

# -*- coding: utf-8 -*-

"""
@Author: xiezizhe
@Date: 30/8/2020 上午12:56
"""

from collections import defaultdict


class Solution:
    def longestZigZag(self, root: TreeNode) -> int:

        levels = [root]
        ret = 0
        dp_r = defaultdict(int)
        dp_l = defaultdict(int)
        while levels:

            nxt = []

            for p in levels:
                if p.left:
                    nxt.append(p.left)
                    dp_l[p.left] = dp_r[p] + 1
                    ret = max(ret, dp_l[p.left])

                if p.right:
                    nxt.append(p.right)
                    dp_r[p.right] = dp_l[p] + 1
                    ret = max(ret, dp_r[p.right])

            levels = nxt

        return ret