二叉树的最长交错路径
LeetCode的第1372题，又开始让人怀疑智商了。
给你一棵以 root 为根的二叉树，二叉树中的交错路径定义如下：
选择二叉树中 任意 节点和一个方向（左或者右）。
如果前进方向为右，那么移动到当前节点的的右子节点，否则移动到它的左子节点。
改变前进方向：左变右或者右变左。
重复第二步和第三步，直到你在树中无法继续移动。
交错路径的长度定义为：访问过的节点数目 - 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
看起来不难，但其实真的不简单，符合我的身份，低端玩家首选----暴力法。果不其然，LeetCode不会让我过得。的确我也觉得很累赘，但是我真的没办法优化了。
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
def longestZigZag(self, root: TreeNode) -> int:
def left(node): #定义函数检测左枝
if not node: return 0
l=0
while node:
if node.left:
if node.left.right: l+=2
else: l+=1
node=node.left.right
else: node=node.left
return l
def right(node): #定义函数检测右枝
if not node: return 0
r=0
while node:
if node.right:
if node.right.left: r+=2
else: r+=1
node=node.right.left
else: node=node.right
return r
stack=[] #用栈遍历整个二叉树
stack.append(root)
max_len=0
while stack!=[]:
root=stack.pop()
if root.left: stack.append(root.left)
if root.right: stack.append(root.right)
if max_len < max(left(root),right(root)):
max_len = max(left(root),right(root))
return max_len
其实暴力法简单易懂，对于新手来说真的还不错。可LeetCode从小就要养成我用脑的习惯，谢谢大佬，再仔细审题，最长交叉路径，加上二叉树的递归，首选动态规划，但是我没有看懂大佬的代码。还有就是深度优先算法，我们只需要传递「当前」这个点应该走的方向（「向左」或者「向右」）dir，以及以这个点结尾的最长交错路径的长度 len。我调整了好久，还是觉得大佬的代码最好，我们还是一起欣赏一下吧。
class Solution:
def longestZigZag(self, root: TreeNode) -> int:
depth=0 #定义原始长度
def across(length,direction,root): #定义函数包含长度，方向，二叉树
nonlocal depth
if not root: return 0
depth=max(depth,length) #保留最大长度
if direction==0: #若方向为左
across(length+1,1,root.left) #下一步方向向右，长度+1
across(1,0,root.right) #下一步方向向左，重置长度
else: #若方向为右
across(1,1,root.left) #下一步方向向左，长度+1
across(length+1,0,root.right) #下一步方向向右，重置长度
return depth
across(0,0,root) #左方向遍历
across(0,1,root) #右方向遍历
return depth
总的来看今天这两道题，都是用了递归函数，还是数学基础有些差啊，后续再多练习吧。昨晚做梦都在想这道题，最后还是跪在大神代码面前，没有系统训练的人啊，今天就这样了！希望大家都有所收获~