文章目錄

• 題目描述
• 思路 & 代碼

題目描述

思路 & 代碼

• 由這個結(jié)論考慮：直徑中一定有一個父結(jié)點，那么當(dāng)前直徑長度就是：
  當(dāng)前父結(jié)點的左子樹深度 + 右子樹深度
• 那么，只要遍歷所有結(jié)點的最長直徑值即可
• 流程：在找每一個結(jié)點的最深值的遍歷過程中維護ans，遍歷結(jié)束后返回ans。

/*** 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 ans = 0;public int diameterOfBinaryTree(TreeNode root) {// 跑結(jié)果，維護ansmaxDepth(root);return ans;}// 函數(shù)功能：返回 root 可達的最深層// 可以遍歷所有結(jié)點的最長直徑int maxDepth(TreeNode root){if(root == null){return 0;}// 取左右子結(jié)點的可達最深層int right = maxDepth(root.right);int left = maxDepth(root.left);// 在這個過程中，維護ans：ans一定是某個結(jié)點的左右子樹結(jié)合成的。ans = Math.max(ans, right + left);// root的maxDepth就是左 or 右的 maxDepth + 1return Math.max(right,left) + 1;} }

• 時間復(fù)雜度O(n)，自底向上把全部結(jié)點遍歷了一遍。
• 無注釋版

class Solution {int ans = 0;public int diameterOfBinaryTree(TreeNode root) {dfs(root);return ans;}public int dfs(TreeNode root) {if(root == null) {return 0;}int left = dfs(root.left);int right = dfs(root.right);ans = Math.max(left + right, ans);return Math.max(left, right) + 1;} }

總結(jié)

以上是生活随笔為你收集整理的【LeetCode笔记】543. 二叉树的直径（Java、dfs、二叉树）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。