[LeetCode]543. Diameter of Binary Tree

树的递归求高度的应用

Posted by JinFei on March 5, 2021

题目描述

Given a binary tree, you need to compute 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.

递归版本解题思路

  • 直径为:求二叉树的一个点到另一个点最长的路径
  • 求出以当前节点为中心,左子树+右子树的高度
  • 然后递归求出当前节点的左子节点,当前节点的右子节点,看哪个大,(经过根节点的直径不一定是最大的)
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    // int res = 0;
    int diameterOfBinaryTree(TreeNode* root) {
        if(root == NULL){
            return 0;
        }
        int res = treeDepth(root -> left) + treeDepth(root -> right);
        return max(res, max(diameterOfBinaryTree(root -> left), diameterOfBinaryTree(root -> right)));
    }
    
    int treeDepth(TreeNode* root){
        if(root == NULL){
            return 0;
        }
        int left = treeDepth(root -> left);
        int right = treeDepth(root -> right);
        return left > right ? left + 1 : right + 1;
    }
};

0305递归版本解题思路

  • 最后递归求最大的时候,应该是比较经过当前root,未经过当前max(left + right, max(root -> left), max(root -> right))