1372. Longest ZigZag Path in a Binary Tree

￡神魔★判官ぃ 2024-04-07 11:54 67阅读 0赞

You are given the `root` of a binary tree.

A ZigZag path for a binary tree is defined as follow:

*  Choose **any** node in the binary tree and a direction (right or left).
 *  If the current direction is right, move to the right child of the current node; otherwise, move to the left child.
 *  Change the direction from right to left or from left to right.
 *  Repeat the second and third steps until you can't move in the tree.

Zigzag length is defined as the number of nodes visited - 1. (A single node has a length of 0).

Return *the longest **ZigZag** path contained in that tree*.

**Example 1:**

![119390777e101e3b71c67a30d6f4727d.png][]

Input: root = [1,null,1,1,1,null,null,1,1,null,1,null,null,null,1,null,1]
    Output: 3
    Explanation: Longest ZigZag path in blue nodes (right -> left -> right).

**Example 2:**

![f603b2bf10a6fa9b717f33b042e092a9.png][]

Input: root = [1,1,1,null,1,null,null,1,1,null,1]
    Output: 4
    Explanation: Longest ZigZag path in blue nodes (left -> right -> left -> right).

**Example 3:**

Input: root = [1]
    Output: 0

题目：给定一棵二叉树，找其中最长的zigzag路。

思路：递归，zigzag路不一定从根节点开始，因此需要记录以每个节点开始的最长zigzag路径，从底部往上回溯。因此从上往下时需要用direction(dir)记录每个节点是左节点还是右节点。如果是左节点（-1代表左节点），则从底部往上时需选择右子节点的zigzag路，如果是右节点（1代表右节点），则需选择其左子节点的zigzag路。根节点用0代表，则选择左子节点或右子节点最长的那条路。代码：

/**
     * Definition for a binary tree node.
     * struct TreeNode {
     *     int val;
     *     TreeNode *left;
     *     TreeNode *right;
     *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
     *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
     *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
     * };
     */
    class Solution {
    public:
        int helper(TreeNode* node, int& res, int dir){
            if(!node) return 0;
            int l = helper(node->left, res, -1);
            int r = helper(node->right, res, 1);
            res = max(res, max(l+1, r+1));
            if(dir == -1) return r+1;
            if(dir == 1) return l+1;
            return max(l,r)+1;
        }
        int longestZigZag(TreeNode* root) {
            int res = 0;
            helper(root, res, 0);
            return res-1;
        }
    };

[119390777e101e3b71c67a30d6f4727d.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/07/f28a5424b5b14e63b6dcd7ba2d24083a.png
[f603b2bf10a6fa9b717f33b042e092a9.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/07/628e06e453cb4d83852af9cc3569a685.png