首页 > 试题广场 >

树上最长单色路径

[编程题]树上最长单色路径

热度指数：1893 时间限制：C/C++ 3秒，其他语言6秒空间限制：C/C++ 32M，其他语言64M
算法知识视频讲解

对于一棵由黑白点组成的二叉树，我们需要找到其中最长的单色简单路径，其中简单路径的定义是从树上的某点开始沿树边走不重复的点到树上的另一点结束而形成的路径，而路径的长度就是经过的点的数量(包括起点和终点)。而这里我们所说的单色路径自然就是只经过一种颜色的点的路径。你需要找到这棵树上最长的单色路径。

给定一棵二叉树的根节点(树的点数小于等于300，请做到O(n)的复杂度)，请返回最长单色路径的长度。这里的节点颜色由点上的权值表示，权值为1的是黑点，为0的是白点。

说明：本题目包含复杂数据结构TreeNode，点此查看相关信息

算法知识视频讲解

Java

重洋

后序遍历，递归返回左右子树较大长度

当前节点计算左右子树长度和，与最大值比较

import java.util.*;

/*
public class TreeNode {
    int val = 0;
    TreeNode left = null;
    TreeNode right = null;
    public TreeNode(int val) {
        this.val = val;
    }
}*/
public class LongestPath {
    int maxLen=0;
    public int findPath(TreeNode root) {
        // write code here
        if(root == null)
            return 0;
        getPath(root);
        return maxLen;
    }
    
    public int getPath(TreeNode root) {
        // write code here
        if(root==null)
            return 0;
        
        int left = getPath(root.left);           //左子树的最大长度
        if(left!=0 && root.val!=root.left.val)
            left=0;
        int right = getPath(root.right);           //左子树的最大长度
        if(right!=0 && root.val!=root.right.val)
            right=0;
        
        //计算最大值
        int Len=left+right+1;
        maxLen=maxLen>Len?maxLen:Len;
        
        //返回左右子树最大长度
        return (Math.max(left, right) + 1);
    }
}

发表于 2019-09-05 10:46:38 回复(0)

Java

StudyOfSlagD

import java.util.*;
/**
 * 对@geassdai的代码进行了解释
 * 从根节点分别往下递归,可以先从左子树往下走,在递归右子树
 */
public class LongestPath {

	int max_path = 0;//最终的结果
	int max_len = 0;//单个子树的长度
	int len = 0;//临时的路径
	public int findPath(TreeNode root) {

		if (root == null)
			return 0;
		setmaxpath(root);
		int tem = max_path;
		max_path = 0;
		max_len = 0;
		return tem;

	}

	public void setmaxpath(TreeNode root) {
		if (root == null)
			return;
		int l;//左子树
		if (root.left != null && root.val == root.left.val) {
			len = 1;
			maxlen(root.left);
			l = max_len;
			max_len = 0;
		} else {
			l = 0;
		}
		System.out.println("l=" + l);
		int r;//从右子树开始往下走
		if (root.right != null && root.val == root.right.val) {
			len = 1;
			maxlen(root.right);
			r = max_len;
			max_len = 0;
		} else {
			r = 0;
		}
		System.out.println("r=" + r);
		if (l + 1 + r > max_path)//加一是因还要把根节点加进去
			max_path = l + 1 + r;
		setmaxpath(root.left);
		setmaxpath(root.right);

	}

	public void maxlen(TreeNode root) {

		if (root == null)
			return;
		if (root.left != null && root.val == root.left.val) {
			len++;
			maxlen(root.left);
		} else if (root.right != null && root.val == root.right.val) {
			len++;
			maxlen(root.right);
		} else if (len > max_len) {
			max_len = len;
			len = 0;
		}

		// return 0;

	}

}

发表于 2016-09-11 11:15:57 回复(0)