LeetCode1372.二叉树中的最长之字形路径对于二叉树定义如下：选择二叉树中的任何节点和方向（右或左）。如果当前方向是右，则移动到当前节点的右子节点，否则移动到左子节点。更改从右到左或从右到左的方向。重复第二步和第三步，直到不能在树中移动。Zigzag长度定义为访问的节点数-1。（单个节点的长度为0）。返回该树中包含的最长之字折线路径。示例1：输入：root=[1,null,1,1,1,null,null,1,1,null,1,null,null,null,1,null,1]输出：3解释：蓝色节点中最长的ZigZag路径（右->左->右）。示例2：输入：root=[1,1,1,null,1,null,null,1,1,null,1]输出：4解释：蓝色节点中最长的之字折线路径（左t->right->left->right）。示例3：输入：root=[1]输出：0约束条件：每棵树最多有50000个节点。每个节点的值介于[1,100]之间。你有一个以根为根的二叉树。二叉树中的交错路径定义如下：选择二叉树中的任意一个节点和一个方向（左或右）。如果前向为右，则移动到当前节点的右子节点，否则移动到其左子节点。改变行进方向：从左到右或从右到左。重复第二步和第三步，直到您无法再在树中移动。交错路径长度定义为：访问的节点数-1（单个节点的路径长度为0）。请返回给定树中最长交错路径的长度。示例1：输入：root=[1,null,1,1,1,null,null,1,1,null,1,null,null,null,1,null,1]输出：3解释：蓝色节点是树中最长的交错路径（右->左->右）。示例2：输入：root=[1,1,1,null,1,null,null,1,1,null,1]输出：4解释：蓝色节点是树中最长的交错路径（左->右->左->右）。示例3：输入：root=[1]输出：0提示：每棵树最多有50000个节点。每个节点的值都在[1,100]之间。ideaDFS记录前一个结点是左结点还是右结点，以及递归时的深度。Python3代码#定义一个二叉树节点。#classTreeNode:#def__init__(self,x):#self.val=x#self.left=None#self.right=Noneclass解决方案：deflongestZigZag(self,root:TreeNode)->int:如果root==None:返回0self.max_=0self.dfs(root,0,0)returnself.max_defdfs(self,root,prev,depth):self.max_=max(depth,self.max_)ifroot.left:#left->leftifprev==0:self.dfs(root.left,0,1)#left->rightelse:self.dfs(root.left,0,depth+1)ifroot.right:#right->rightifprev==1:self.dfs(root.right,1,1)#right->leftelse:self.dfs(root.right,1,depth+1)代码地址GitHub链接
