赞
踩
java数据结构与算法刷题目录(剑指Offer、LeetCode、ACM)-----主目录-----持续更新(进不去说明我没写完):https://blog.csdn.net/grd_java/article/details/123063846 |
---|
解题思路:时间复杂度O(n),空间复杂度O(n) |
---|
- 利用深度优先遍历,从最底下的结点开始,依次和左右儿子进行比较
- 如果当前结点,和左儿子相同,则左子树路径长度+1
- 如果和右儿子相同,右子树路径长度+1
- 将左右子树和当前结点相连后的路径长度保存起来
- 然后继续递归遍历,上面将相连的保存了,接下来就是不连左右子树,那么就返回左右子树长的一条。
代码 |
---|
/** * 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 max; public int longestUnivaluePath(TreeNode root) { max = 0; dfs(root); return max; } public int dfs(TreeNode root) { if(root == null) return 0; //以每一个结点为根 int left = dfs(root.left);//获取左子树的相同结点路径长度 int right = dfs(root.right); int _left = 0, _right = 0;//记录路径长度 //如果左或右子树和当前结点相同,记录连接左右子树分别的路径长度 if(root.left != null && root.left.val == root.val) _left = left+1; if(root.right != null && root.right.val == root.val) _right = right+1; //max中保存和当前结点相连后的路径长度,保存大的 max = Math.max(max,_left+_right); return Math.max(_left,_right);//返回时,返回和左右子树相连后,较长的路径 } }
解题思路:时间复杂度O(n),空间复杂度O(n) |
---|
- 一个细节的改变,可以省下一些判断
- 每次深度优先遍历时,传入当前结点的值(下一个结点的父结点)
- 如果当前结点和父结点值相同,就返回较长路径长度
- 不断记录相连后的最大路径
代码 |
---|
class Solution { int max = 0; public int longestUnivaluePath(TreeNode root) { dfs(root,-1); return max; } //root是当前结点,parentVal是父结点的值 public int dfs(TreeNode root,int parentVal) { if(root == null) return 0;//如果root == null 说明没有路径 int left = dfs(root.left,root.val);//获取左子树的和当前结点值相同的连续路径长度 int right = dfs(root.right,root.val); max = Math.max(max,left+right);//保存左右子树和当前结点相连后的路径长度,保存大的 //如果当前结点和父结点相同,返回较长路径+1,其中+1是加上自己本身后的路径长度,因为left和right是不加他自己的路径长度 if(root.val == parentVal) return Math.max(left,right)+1; return 0;//返回时,返回和左右子树相连后,较长的路径 } }
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。