前言：
目前同学们对“遍历二叉树js”都比较关心，看官们都需要了解一些“遍历二叉树js”的相关内容。那么小编也在网上网罗了一些对于“遍历二叉树js””的相关知识，希望姐妹们能喜欢，朋友们快快来学习一下吧！简介： 算法面试真题详解：二叉树最长连续序列
给一棵二叉树，找到最长连续路径的长度。
这条路径是指 任何的节点序列中的起始节点到树中的任一节点都必须遵循 父-子 联系。最长的连续路径必须是从父亲节点到孩子节点（不能逆序）。
样例1:
输入:{1,#,3,2,4,#,#,#,5}输出:3说明:这棵树如图所示 1 \ 3 / \ 2 4 \ 5最长连续序列是3-4-5，所以返回3.样例2:输入:{2,#,3,2,#,1,#}输出:2说明:这棵树如图所示： 2 \ 3 / 2 / 1最长连续序列是2-3，而不是3-2-1，所以返回2.解题思路本题在二叉树遍历的基础上，统计树上的信息，可以用深度优先搜索递归解决。每次统计完某个节点为端点最长链和子树中最长链的信息，并返回父节点，这样自底向上进行计算。如果某个节点能和子节点组成链，那么它能组成的最长链为子节点能组成的最长链长度加上一。
代码思路
递归步骤：
如果节点为空，返回(0, 0)。令rootMaxLength = 1，代表该节点的最长链长度。令subtreeMaxLength = 1，代表子树最长链长度。递归获得左子树信息leftResult，更新rootMaxLength和subMaxLength。递归获得右子树信息rightResult，更新rootMaxLength和subMaxLength。返回(rootMaxLength, subMaxLength)。复杂度分析
设V为二叉树的节点数。
时间复杂度每个节点被遍历1遍，时间复杂度为O(N)。空间复杂度递归遍历二叉树的空间开销取决于二叉树的深度，最劣情况树是一条链，所以时间复杂度为O(N)。
public class Solution { /** * @param root: the root of binary tree * @return: the length of the longest consecutive sequence path */ public int longestConsecutive(TreeNode root) { int[] result = helper(root); return result[1]; } // 返回以 root 为端点的最长链，和以 root 为根的子树的最长链 int[] helper(TreeNode root) { // 递归出口 if (root == null) { return new int[2]; } int rootMaxLength = 1; int subtreeMaxLength = 1; // 处理左子树的信息 int[] leftResult = helper(root.left); if (root.left != null && root.val + 1 == root.left.val) { rootMaxLength = Math.max(rootMaxLength, leftResult[0] + 1); } subtreeMaxLength = Math.max(subtreeMaxLength, leftResult[1]); // 处理右子树的信息 int[] rightResult = helper(root.right); if (root.right != null && root.val + 1 == root.right.val) { rootMaxLength = Math.max(rootMaxLength, rightResult[0] + 1); } subtreeMaxLength = Math.max(subtreeMaxLength, rightResult[1]); // 考虑当前节点为端点的链是子树最长链的情况 subtreeMaxLength = Math.max(subtreeMaxLength, rootMaxLength); int[] result = new int[2]; result[0] = rootMaxLength; result[1] = subtreeMaxLength; return result; }}原文：
版权声明：
本站文章均来自互联网搜集，如有侵犯您的权益，请联系我们删除，谢谢。
标签： #遍历二叉树js
