1372_二叉树中的最长交错路径

类型：树

• 1372. 二叉树中的最长交错路径 💛

  https://leetcode-cn.com/problems/longest-zigzag-path-in-a-binary-tree/

  ❓ 返回一棵树中最长的交错路径（Z形路径）长度。（不一定要从根结点出发。）

  

  

  💡 DFS

  我们在 DFS 的过程中，维护当前的方向 direction。我们可以用 -1 和 1 来表示接下来要向左或向右。

  • 如果我们接下来确实是要向左了，那么我们在递归遍历左子树的时候就可以使长度 + 1，否则以长度为 0 递归遍历左子树。
  • 如果我们接下来确实是要向右了，那么我们在递归遍历右子树的时候就可以使长度 + 1，否则以长度为 0 递归遍历右子树。

  刚开始的时候，我们使 direction 为 0，即 direction 即不等于左，也不等于右，这样就会分别发起向左和向右的遍历。

  class Solution:
      def __init__(self):
          self.maxLength = 0
  
      def dfs(self, node, direction, length):
          if length > self.maxLength:
              self.maxLength = length
  
          direction = direction * -1
          if node.left:
              self.dfs(node.left, -1, length + 1 if direction == -1 else 1)
          if node.right:
              self.dfs(node.right, 1, length + 1 if direction == 1 else 1)
  
  
      def longestZigZag(self, root: TreeNode) -> int:
          if not root: return 0
          self.dfs(root, 0, 0)
          return self.maxLength

  时间复杂度：O(n)，空间复杂度：O(1)