leetcode543：二叉树的直径

题目链接

leetcode

题目描述

给你一棵二叉树的根节点，返回该树的 直径 。
二叉树的 直径 是指树中任意两个节点之间最长路径的 长度 。这条路径可能经过也可能不经过根节点 root 。
两节点之间路径的 长度 由它们之间边数表示。

C++ 代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
#include <iostream>
#include <vector>
#include <stack>
#include <queue>
#include <unordered_map>
#include <algorithm>
using namespace std;

// 二叉树结点的定义
struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode() : val(0), left(nullptr), right(nullptr) {}
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
    TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};

const int NULL_NODE = -1001;

// 辅助函数：创建二叉树
TreeNode* createTree(const vector<int>& nums) {
    if (nums.empty()) return nullptr;

    TreeNode* root = new TreeNode(nums[0]);
    queue<TreeNode*> queue;
    queue.push(root);
    int i = 1;
    while (!queue.empty() && i < nums.size()) {
        TreeNode* node = queue.front(); queue.pop();
        if (nums[i] != NULL_NODE) {
            node->left = new TreeNode(nums[i]);
            queue.push(node->left);
        }
        i ++;
        if (i < nums.size() && nums[i] != NULL_NODE) {
            node->right = new TreeNode(nums[i]);
            queue.push(node->right);
        }
        i ++;
    }

    return root;
}

// 辅助函数：层序遍历打印二叉树
void levelOrderTraversal(TreeNode* root) {
    if (root == nullptr) return;

    queue<TreeNode*> queue;
    queue.push(root);
    while (!queue.empty()) {
        TreeNode* node = queue.front(); queue.pop();
        cout << node->val << " ";
        if (node->left != nullptr) queue.push(node->left);
        if (node->right != nullptr) queue.push(node->right);
    }
    cout << endl;
}

// 辅助函数：释放二叉树
void deleteTree(TreeNode* root) {
    if (root == nullptr) return;
    deleteTree(root->left);
    deleteTree(root->right);
    delete root;
}

/*
    二叉树的直径，就是左右子树的最大深度之和。
    对每个结点计算左右子树的最大高度，求出每个结点的直径，从而求出最大直径。

    时间复杂度：O(n)
        其中 n 为二叉树的结点数。
        遍历一棵二叉树的时间复杂度，每个结点只被访问一次。
    空间复杂度：O(n)
        在递归过程中需要为每一层递归函数分配栈空间，需要额外空间取决于递归的深度，
        递归深度为二叉树的高度，并且每次递归调用函数只用了常数个变量。
        在最坏情况下，二叉树退化为一条链，此时递归栈的深度为 n，所以空间复杂度为 O(n)。
        在平衡二叉树的情况下，递归栈的深度为 O(logn)，平均空间复杂度接近 O(logn)。
*/
class Solution {
public:
    int diameterOfBinaryTree(TreeNode* root) {
        dfs(root);
        return res;
    }

    int dfs(TreeNode* node) {
        if (node == nullptr) return 0;

        int leftMax = dfs(node->left);
        int rightMax = dfs(node->right);
        // 后序遍历位置：计算最大直径
        res = max(res, leftMax + rightMax);
        return 1 + max(leftMax, rightMax);
    }

private:
    int res;
};

int main() {
    // 示例输入
    Solution solution;
    vector<int> nums = {1, 2, 3, 4, 5};

    // 创建二叉树
    TreeNode* root = createTree(nums);
    levelOrderTraversal(root);

    // 计算直径
    int result = solution.diameterOfBinaryTree(root);
    // 打印结果
    cout << "Diameter of Binary Tree: " << result << endl;

    // 释放内存
    deleteTree(root);

    return 0;
}

Golang 代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
package main

import (
	"fmt"
	"math"
)

// 定义二叉树节点
type TreeNode struct {
    Val   int
    Left  *TreeNode
    Right *TreeNode
}

// 创建二叉树
func createTree(values []int) *TreeNode {
	if len(values) == 0 {
		return nil
	}
	root := &TreeNode{Val: values[0]}
	queue := []*TreeNode{root}
	i := 1
	for i < len(values) {
		node := queue[0]
		queue = queue[1:]

		if i < len(values) && values[i] != -1 {
			node.Left = &TreeNode{Val: values[i]}
			queue = append(queue, node.Left)
		}
		i++

		if i < len(values) && values[i] != -1 {
			node.Right = &TreeNode{Val: values[i]}
			queue = append(queue, node.Right)
		}
		i++
	}
	return root
}

// 打印二叉树（层序遍历）
func printTree(root *TreeNode) string {
	if root == nil {
		return "[]"
	}
	result := []int{}
	queue := []*TreeNode{root}
	for len(queue) > 0 {
		node := queue[0]
		queue = queue[1:]
		if node == nil {
			result = append(result, -1)
			continue
		}
		result = append(result, node.Val)
		queue = append(queue, node.Left)
		queue = append(queue, node.Right)
	}
	// 去掉尾部的 -1
	for len(result) > 0 && result[len(result)-1] == -1 {
		result = result[:len(result)-1]
	}
	return fmt.Sprintf("%v", result)
}

/*
    基本思路：递归实现
        从根节点开始递归遍历二叉树。
        对于每个节点，计算其左右子树的深度，并更新直径（左右子树深度之和的最大值）。
        同时，返回当前节点的深度。
    
    时间复杂度：O(n)
        其中 n 是二叉树的节点数量，遍历二叉树的每个节点一次，所以时间复杂度为 O(n)。
    空间复杂度：O(n)
        取决于递归调用栈的深度。
        在最坏情况下，二叉树退化为一条链，此时递归栈的深度为 n，所以空间复杂度为 O(n)。
        在平衡二叉树的情况下，递归栈的深度为 O(logn)，平均空间复杂度接近 O(logn)。
*/
// 计算以当前节点为根的子树的深度和直径
func diameterOfBinaryTree(root *TreeNode) int {
    var maxDiameter int
    depth(root, &maxDiameter)
    return maxDiameter
}

// 计算深度，并更新直径
func depth(node *TreeNode, diameter *int) int {
    if node == nil {
        return 0
    }

    // 递归计算左右子树的深度
    leftDepth := depth(node.Left, diameter)
    rightDepth := depth(node.Right, diameter)
    // 更新最大直径
    // if leftDepth + rightDepth > *diameter {
    //     *diameter = leftDepth + rightDepth
    // }
    *diameter = max(*diameter, leftDepth + rightDepth)
    // 返回当前节点的深度
    // if leftDepth > rightDepth {
    //     return leftDepth + 1
    // }
    // return rightDepth + 1
    return 1 + max(leftDepth, rightDepth)
}

// 思路同上
func diameterOfBinaryTree_1(root *TreeNode) int {
    maxDiameter := 0

    // 辅助函数，计算每个节点的最大深度
    var depth func(*TreeNode) int
    depth = func(node *TreeNode) int {
        if node == nil {
            return 0
        }

        // 递归计算左右子树的深度
        leftDepth := depth(node.Left)
        rightDepth := depth(node.Right)

        // 更新最大直径
        maxDiameter = int(math.Max(float64(maxDiameter), float64(leftDepth + rightDepth)))
        // 返回当前节点的深度
        return 1 + int(math.Max(float64(leftDepth), float64(rightDepth)))
    }

    depth(root)
    return maxDiameter
}

func main() {
    // 测试用例
    testCases := []struct {
        values   []int
        expected int
    }{
        {
            values:   []int{1,2,3,4,5},
            expected: 3,
        },
        {
            values:   []int{1,2},
            expected: 1,
        },
    }

    for i, tc := range testCases {
        root := createTree(tc.values)
        fmt.Printf("Test Case %d, Input: values = %v\n", i+1, printTree(root))
        result := diameterOfBinaryTree(root)
        
        if result == tc.expected {
            fmt.Printf("Test Case %d, Output: %d, PASS\n", i+1, result)
        } else {
            fmt.Printf("Test Case %d, Output: %d, FAIL (Expected: %d)\n", i+1, result, tc.expected)
        }
    }
}
#leetcode
leetcode543：二叉树的直径
https://lcf163.github.io/2024/05/26/leetcode543：二叉树的直径/
作者
乘风的小站
发布于
2024年5月26日
许可协议