求任意二叉树中第一条最长的路径长度,并输出此路径上各结点的值

发布网友发布时间：2022-04-28 10:32

共2个回答

懂视网时间：2022-05-10 18:46

解题思路：递归算法

/**
public class TreeNode {
 int val = 0;
 TreeNode left = null;
 TreeNode right = null;

 public TreeNode(int val) {
 this.val = val;

 }

}
*/import java.lang.Math;public class Solution {
 public int TreeDepth(TreeNode pRoot)
 { if(pRoot == null){  return 0;
 } int left = TreeDepth(pRoot.left); int right = TreeDepth(pRoot.right); return Math.max(left, right) + 1;
 }
}

热心网友时间：2022-05-10 15:54

void LongestPath(BiTree bt)//求二叉树中的第一条最长路径长度
{BiTree p=bt,l[],s[];
//l, s是栈，元素是二叉树结点指针，l中保留当前最长路径中的结点
int i，top=0,tag[],longest=0;
while(p || top>0)
{while(p) {s[++top]=p；tag[top]=0; p=p->Lc;} //沿左分枝向下
if(tag[top]==1) //当前结点的右分枝已遍历
{if(!s[top]->Lc && !s[top]->Rc) //只有到叶子结点时，才查看路径长度
if(top>longest)
{for(i=1;i<=top;i++) l[i]=s[i]; longest=top; top--;}
//保留当前最长路径到l栈，记住最高栈顶指针，退栈
}
else if(top>0) {tag[top]=1; p=s[top].Rc;} //沿右子分枝向下
}//while(p!=null||top>0)
}//结束LongestPath