Leetcode 1372. 二叉树中的最长交错路径（DAY 17）

原题题目

代码实现（暴力解法 超时）

/*** Definition for a binary tree node.* struct TreeNode {* int val;* struct TreeNode *left;* struct TreeNode *right;* };*/int maxpaths;void visit(struct TreeNode* root,int direction,int paths)
{
    if(root){
    if(paths > maxpaths)maxpaths = paths;if(direction == 1)visit(root->right,0,paths+1);elsevisit(root->left,1,paths+1);}
}void go(struct TreeNode* root)
{
    if(root){
    visit(root,0,0);visit(root,1,0);go(root->left);go(root->right);}
}int longestZigZag(struct TreeNode* root){
    if(!root)return 0;maxpaths = 0;go(root);return maxpaths;
}

代码实现（递归继承法 只遍历一次）

/*** Definition for a binary tree node.* struct TreeNode {* int val;* struct TreeNode *left;* struct TreeNode *right;* };*/int maxpaths;void visit(struct TreeNode* root,int direction,int paths)
{
    if(root){
    if(paths > maxpaths)maxpaths = paths;if(!direction){
    visit(root->left,1,paths+1);visit(root->right,0,1);}else{
    visit(root->left,1,1);visit(root->right,0,paths+1);}}
}int longestZigZag(struct TreeNode* root){
    if(!root)return 0;maxpaths = 0;visit(root,0,0);    visit(root,1,0);return maxpaths;
}