[LeetCode] 1372. Longest ZigZag Path in a Binary Tree 二叉樹中的最長交錯路徑

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:

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

Example 2:

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

Constraints:

The number of nodes in the tree is in the range [1, 5 * 104].
1 <= Node.val <= 100

這道題給了一棵二叉樹，說是讓找一條最長的‘之’字路線，LeetCode 上關于 ZigZag 的題目還有好幾道呢，比如 ZigZag Conversion，Binary Tree Zigzag Level Order Traversal，Path In Zigzag Labelled Binary Tree，和 Decrease Elements To Make Array Zigzag，這里的‘之’字路線，對于二叉樹來說，就是左右子結點交替變換著，題目中給的例子也有圖片展示，應該不難理解。這道題的本質還是一個二叉樹的遍歷問題，由于是求路徑，那么就比較適合使用先序遍歷，也就首選遞歸來解題。如何來寫遞歸呢，難點還是要解決‘之’字遍歷的問題，先來分析，若當前結點是其父結點的左子結點，那么只要當前結點的右子結點存在，‘之’字路經長度就可以加1。還有一種情況，若當前結點是其父結點的右子結點，而且當前結點的右子結點也存在，這時候就要以當前結點為起點，重新開始統計‘之’字路經長度，因為題目中并沒有說路徑必須要以根結點為起點，任意一個結點都可以當作起始結點。

分析到了這里，就可以嘗試來寫遞歸來，通過之前的分析，可以知道遞歸函數需要一些額外的參數，比如當前已經統計的‘之’字路經長度，還有全局的最長路徑長度，同時還需要一個變量標記當前‘之’字路經的方向，這里用個整型數變量 dir，其中0表示往左，1表示往右。在主函數中，兩個方向分別要調用一次遞歸函數。在遞歸函數中，首先判空，然后用當前路徑長度 curLen 來更新最終結果 res。然后判斷變量 dir，若 dir 為0，則說明目前往左走可以增加路徑長度，則對左子結點調用遞歸函數，為了延長路徑，之后應該往右走，所以第二個參數傳1，路徑長度增加1。同時也要當前結點為路徑起點再統計一次，則可以對右子結點調用遞歸，第二個參數就傳0，路徑長度重置為1。若 dir 為1，則說明目前往右走可以增加路徑長度，則對右子結點調用遞歸函數，為了延長路徑，之后應該往左走，所以第二個參數傳0，路徑長度增加1。同時也要當前結點為路徑起點再統計一次，則可以對左子結點調用遞歸，第二個參數就傳1，路徑長度重置為1，參見代碼如下：

解法一：

class Solution {
public:
    int longestZigZag(TreeNode* root) {
        int res = 0;
        dfs(root, 0, 0, res);
        dfs(root, 1, 0, res);
        return res;
    }
    void dfs(TreeNode* node, int dir, int curLen, int& res) {
        if (!node) return;
        res = max(res, curLen);
        if (dir == 0) {
            dfs(node->left, 1, curLen + 1, res);
            dfs(node->right, 0, 1, res);
        } else {
            dfs(node->right, 0, curLen + 1, res);
            dfs(node->left, 1, 1, res);
        }
    }
};

我們再來看一種解法，這種解法的思路是，同時記錄當前結點接下來要分別去左邊和右邊的‘之’字路經長度。這里也是要用遞歸函數，新建了兩個變量 left 和 right，其中 left 表示接下來要去左子結點時當前的路徑長度，同理，right 表示接下來要去右子結點時當前的路徑長度。在遞歸函數中，首先判空，然后用 left 和 right 值來更新結果 res。接下來對左子結點調用遞歸函數，此時因為接下來是往左走的，那么新的 left 就要重置為0，新的 right 值為原來的 left 加1，同理，對右子結點調用遞歸函數，此時因為接下來是往右走的，那么新的 right 就要重置為0，新的 left 值為原來的 right 加1，參見代碼如下：

解法二：

class Solution {
public:
    int longestZigZag(TreeNode* root) {
        int res = 0, left = 0, right = 0;
        dfs(root, left, right, res);
        return res;
    }
    void dfs(TreeNode* node, int left, int right, int& res) {
        if (!node) return;
        res = max(res, max(left, right));
        dfs(node->left, 0, left + 1, res);
        dfs(node->right, right + 1, 0, res);
    }
};

Github 同步地址:

https://github.com/grandyang/leetcode/issues/1372

類似題目：

Zigzag Grid Traversal With Skip

參考資料：

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

https://leetcode.com/problems/longest-zigzag-path-in-a-binary-tree/solutions/1159847/c-easy-simple-traversal/

https://leetcode.com/problems/longest-zigzag-path-in-a-binary-tree/solutions/534418/java-c-dfs-solution-with-comment-o-n-clean-code/

LeetCode All in One 題目講解匯總(持續更新中...)