526互联

[LeetCode] 1372. Longest ZigZag Path in a Binary Tree

发布时间 2023-04-22 07:01:02作者: CNoodle

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,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

二叉树中的最长交错路径。

给你一棵以 root 为根的二叉树，二叉树中的交错路径定义如下：

选择二叉树中 任意 节点和一个方向（左或者右）。
如果前进方向为右，那么移动到当前节点的的右子节点，否则移动到它的左子节点。
改变前进方向：左变右或者右变左。
重复第二步和第三步，直到你在树中无法继续移动。
交错路径的长度定义为：访问过的节点数目 - 1（单个节点的路径长度为 0 ）。

请你返回给定树中最长 交错路径 的长度。

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/longest-zigzag-path-in-a-binary-tree
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路是前序遍历。因为要看最长的路径，肯定需要遍历整棵树，无非是怎样遍历罢了。注意题目的要求，在二叉树的任何节点，你其实是可以自由选择到底是往左走还是往右走的，举个例子，哪怕你上一步走的是左边，这一步应该走右边，你当前这一步还是可以选择走左边的。所以这里我们需要在helper函数里多一个 boolean 变量记录此时应该是往左还是往右。其余思路参见代码注释。

时间O(n)

空间O(n)

Java实现

 1 /**
 2  * Definition for a binary tree node.
 3  * public class TreeNode {
 4  *     int val;
 5  *     TreeNode left;
 6  *     TreeNode right;
 7  *     TreeNode() {}
 8  *     TreeNode(int val) { this.val = val; }
 9  *     TreeNode(int val, TreeNode left, TreeNode right) {
10  *         this.val = val;
11  *         this.left = left;
12  *         this.right = right;
13  *     }
14  * }
15 **/    
16 class Solution {
17     int res = 0;
18 
19     public int longestZigZag(TreeNode root) {
20         dfs(root, 0, false);
21         return res;
22     }
23 
24     // isLeft 记录是该往左走还是往右走
25     private void dfs(TreeNode root, int count, boolean isLeft) {
26         // 如果该往左走
27         if (isLeft) {
28             // 且左子树不为空，则count + 1
29             if (root.left != null) {
30                 dfs(root.left, count + 1, false);
31             }
32             // 如果往右走了，count则要重新开始计算
33             if (root.right != null) {
34                 dfs(root.right, 1, true);
35             }
36         }
37         // 如果该往右走
38         else {
39             // 且右子树不为空，则count + 1
40             if (root.right != null) {
41                 dfs(root.right, count + 1, true);
42             }
43             // 如果往左走了，count则要重新开始计算
44             if (root.left != null) {
45                 dfs(root.left, 1, false);
46             }
47         }
48         res = Math.max(res, count);
49     }
50 }

 

LeetCode 题目总结