Re: [閒聊] 每日LeetCode
1372. Longest ZigZag Path in a Binary Tree
給你一個二元樹，找出這個二元樹裡的Z字型路徑最大長度。
Example :
https://assets.leetcode.com/uploads/2020/01/22/sample_1_1702.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).
https://assets.leetcode.com/uploads/2020/01/22/sample_2_1702.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).
思路：
1.用dfs遍歷樹，把上一層的最大Z字型長度按照方向交錯傳給下一層，並在途中不斷更
新 ans。
Java Code：
-------------------------------------------------------------
class Solution {
private int ans;
public int longestZigZag(TreeNode root) {
ans = 0;
dfs(root, 0, 0);
return ans;
}
public void dfs(TreeNode root, int l, int r) {
if (root == null) {
return;
}
ans = Math.max(ans, Math.max(l, r));
dfs(root.left, r + 1, 0);
dfs(root.right, 0, l + 1);
}
}
-------------------------------------------------------------
--
https://i.imgur.com/tdaniED.jpg
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 122.100.75.86 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1681891899.A.247.html
討論串 (同標題文章)
完整討論串 (本文為第 298 之 719 篇)：