LeetCode_二叉树_中等_1372.二叉树中的最长交错路径

逃离我推掉我的手 2023-10-16 13:48 15阅读 0赞

#### 目录 ####

*  1.题目
 *  2.思路
 *  3.代码实现（Java）

## 1.题目 ##

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

*  选择二叉树中 任意 节点和一个方向（左或者右）。
 *  如果前进方向为右，那么移动到当前节点的的右子节点，否则移动到它的左子节点。
 *  改变前进方向：左变右或者右变左。
 *  重复第二步和第三步，直到你在树中无法继续移动。

交错路径的长度定义为：访问过的节点数目 - 1（单个节点的路径长度为 0 ）。  
请你返回给定树中最长交错路径的长度。

**示例 1：**

![在这里插入图片描述][d2553004044343cd9c8aa55e94c32d4e.png]

输入：root = \[1,null,1,1,1,null,null,1,1,null,1,null,null,null,1,null,1\]  
输出：3  
解释：蓝色节点为树中最长交错路径（右 -> 左 -> 右）。

**示例 2：**

![在这里插入图片描述][2074142badc84f79a7aacc5a77210c65.png]

输入：root = \[1,1,1,null,1,null,null,1,1,null,1\]  
输出：4  
解释：蓝色节点为树中最长交错路径（左 -> 右 -> 左 -> 右）。

**示例 3：**  
输入：root = \[1\]  
输出：0

**提示：**  
每棵树最多有 50000 个节点。  
每个节点的值在 \[1, 100\] 之间。

## 2.思路 ##

（1）DFS  
参考[本题官网题解][Link 1]。

## 3.代码实现（Java） ##

//思路1————DFS
    /**
     * Definition for a binary tree node.
     * public class TreeNode {
     *     int val;
     *     TreeNode left;
     *     TreeNode right;
     *     TreeNode() {}
     *     TreeNode(int val) { this.val = val; }
     *     TreeNode(int val, TreeNode left, TreeNode right) {
     *         this.val = val;
     *         this.left = left;
     *         this.right = right;
     *     }
     * }
     */
    class Solution {
        
    
        int res;
    
        public int longestZigZag(TreeNode root) {
        
            if (root == null) {
        
                return 0;
            }
            res = 0;
            dfs(root, true, 0);
            dfs(root, false, 0);
            return res;
        }
    
        private void dfs(TreeNode root, boolean dir, int len) {
        
            res = Math.max(res, len);
            if (dir) {
        
                //上一步方向为左
                if (root.left != null) {
        
                    dfs(root.left, true, 1);
                }
                if (root.right != null) {
        
                    dfs(root.right, false, len + 1);
                }
            } else {
        
                //上一步方向为右
                if (root.left != null) {
        
                    dfs(root.left, true, len + 1);
                }
                if (root.right != null) {
        
                    dfs(root.right, false, 1);
                }
            }
        }
    }

[d2553004044343cd9c8aa55e94c32d4e.png]: https://img-blog.csdnimg.cn/d2553004044343cd9c8aa55e94c32d4e.png
[2074142badc84f79a7aacc5a77210c65.png]: https://img-blog.csdnimg.cn/2074142badc84f79a7aacc5a77210c65.png
[Link 1]: https://leetcode.cn/problems/longest-zigzag-path-in-a-binary-tree/solutions/147425/er-cha-shu-zhong-de-zui-chang-jiao-cuo-lu-jing-b-2/