LeetCode - Easy - 543. Diameter of Binary Tree-蒲公英云

LeetCode - Easy - 543. Diameter of Binary Tree

r囧r小猫 2022-10-18 01:52 306阅读 0赞

Topic

Tree

Description

https://leetcode.com/problems/diameter-of-binary-tree/

Given the root of a binary tree, return the length of the diameter of the tree.

The diameter of a binary tree is the length of the longest path between any two nodes in a tree. This path may or may not pass through the root.

The length of a path between two nodes is represented by the number of edges between them.

Example 1:

Input: root = [1,2,3,4,5]
Output: 3
Explanation: 3is the length of the path [4,2,1,3] or [5,2,1,3].

Example 2:

Input: root = [1,2]
Output: 1

Constraints:

The number of nodes in the tree is in the range [ 1 , 1 0 4 ] [1, 10^4] [1,104].
− 100 < = N o d e . v a l < = 100 -100 <= Node.val <= 100 −100<=Node.val<=100

Analysis

用到二叉树后序遍历模式。

Submission

public class DiameterOfBinaryTree { 
    public int diameterOfBinaryTree(TreeNode root) { 
        int[] max = { 0};
        diameterOfBinaryTree(root, max);
        return max[0];
    }
    private int diameterOfBinaryTree(TreeNode node, int[] max) { 
        if(node == null) return 0;
        int left = 0, right = 0;
        if(node.left != null) 
            left = diameterOfBinaryTree(node.left, max) + 1;
        if(node.right != null)
            right = diameterOfBinaryTree(node.right, max) + 1;
        max[0] = Math.max(max[0], left + right);
        return Math.max(left, right);
    }
}

Test

import static org.junit.Assert.*;
import org.junit.Test;
import com.lun.util.BinaryTree;
public class DiameterOfBinaryTreeTest { 
    @Test
    public void test() { 
        DiameterOfBinaryTree obj = new DiameterOfBinaryTree();
        assertEquals(3, obj.diameterOfBinaryTree(BinaryTree.integers2BinaryTree(1, 2, 3, 4, 5)));
        assertEquals(1, obj.diameterOfBinaryTree(BinaryTree.integers2BinaryTree(1, 2)));
        assertEquals(8, obj.diameterOfBinaryTree(BinaryTree.integers2BinaryTree(4,-7,-3,null,null,//
            -9,-3,9,-7,-4,null,6,null,-6,-6,null,null,0,6,5,null,9,null,null,-1,-4,null,null,null,-2)));
    }
}