刷题笔记4-二叉树

（一）

翻转二叉树 226

二叉树展开为链表 114

填充每个节点的下一个右侧节点指针 116

【翻转二叉树】

给你一棵二叉树的根节点 root ，翻转这棵二叉树，并返回其根节点。

1
2
3
4
5
6
7
8
9
10
11
class Solution {
   public:
    TreeNode* invertTree(TreeNode* root) {
        if (root == nullptr) return nullptr;
        TreeNode* right = invertTree(root->left);
        TreeNode* left = invertTree(root->right);
        root->left = left;
        root->right = right;
        return root;
    }
};

【填充每个节点的下一个右侧节点指针】

给定一个 完美二叉树 ，其所有叶子节点都在同一层，每个父节点都有两个子节点。二叉树定义如下：

1
2
3
4
5
6
struct Node {
  int val;
  Node *left;
  Node *right;
  Node *next;
}

填充它的每个 next 指针，让这个指针指向其下一个右侧节点。如果找不到下一个右侧节点，则将 next 指针设置为 NULL。

初始状态下，所有 next 指针都被设置为 NULL。

【分析】

这道题的递归解法十分巧妙，而迭代解法更为自然

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
class Solution {
   public:
    /**
     * @brief 借用队列实现的迭代解法
     *
     * @param root
     * @return Node*
     */
    Node* connect1(Node* root) {
        if (root == nullptr) return nullptr;
        queue<Node*> q;
        q.push(root);
        q.push(nullptr);  // 用nullptr标志一层的结束
        while (q.size() > 1) {
            Node* n = q.front();
            q.pop();
            if (n != nullptr) {
                n->next = q.front();
                if (n->left) q.push(n->left);
                if (n->right) q.push(n->right);
            } else {
                q.push(nullptr);
            }
        }
        return root;
    }

    /**
     * @brief 递归解法
     *
     * @param root
     * @return Node*
     */
    Node* connect(Node* root) {
        if (root == nullptr) return root;
        root->next = nullptr;
        connectionTwoNode(root->left, root->right);
        return root;
    }
	// 采用两个结点的递归
    // 但是这个递归会存在重叠部分
    void connectionTwoNode(Node* node1, Node* node2) {
        if (node1 == nullptr || node2 == nullptr) return;
        node1->next = node2;
        node2->next = nullptr;
        connectionTwoNode(node1->left, node1->right);
        connectionTwoNode(node1->right, node2->left);
        connectionTwoNode(node2->left, node2->right);
    }
};

【二叉树展开为链表】

给你二叉树的根结点 root ，请你将它展开为一个单链表：

  • 展开后的单链表应该同样使用 TreeNode ，其中 right 子指针指向链表中下一个结点，而左子指针始终为 null 。
  • 展开后的单链表应该与二叉树 先序遍历 顺序相同。

【思路】

先将root的左子树部分展开为链表，再将右子树部分展开为链表，最后进行连接。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
   public:
    void flatten(TreeNode* root) {
        if (root == nullptr) return;

        flatten(root->left);
        flatten(root->right);

        connect(root);
    }
	// 将左边的链表、根节点、右边的链表进行连接
    void connect(TreeNode* root) {
        if (root->left == nullptr) return;
        // 找到左子节点的最右子节点
        TreeNode* rightConnector = root->left;
        while (rightConnector->right != nullptr) {
            rightConnector = rightConnector->right;
        }

        rightConnector->right = root->right;
        root->right = root->left;
        root->left = nullptr;
    }
};

总结

二叉树的递归解法需要从大局来看，先将整个二叉树看成是 左子树、根节点、右子树 三部分，然后考虑应该对左子树和右子树如何递归操作，以及和根节点如何整合。不要局限于递归的细节，而是用整体来看待。但是对于最基本的base-case还是要考虑清楚以及是否能正确执行。

（二）

最大二叉树 654

从前序与中序遍历序列构造二叉树 105

从中序与后序遍历序列构造二叉树 106

【最大二叉树】

给定一个不重复的整数数组 nums 。 最大二叉树 可以用下面的算法从 nums 递归地构建:

  1. 创建一个根节点，其值为 nums 中的最大值。
  2. 递归地在最大值 左边 的 子数组前缀上 构建左子树。
  3. 递归地在最大值 右边 的 子数组后缀上 构建右子树。

返回 nums 构建的 *最大二叉树* 。

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
class Solution {
   public:
    TreeNode* constructMaximumBinaryTree(vector<int>& nums) {
        return constructMaximumBinaryTreeHelper(nums, 0, nums.size() - 1);
    }

    TreeNode* constructMaximumBinaryTreeHelper(vector<int>& nums, int left,
                                               int right) {
        if (left > right) return nullptr;
        // 找到[left, right]部分的最大元素
        int idx = left;
        int val = nums[left];
        for (int i = left; i <= right; i++) {
            if (nums[i] > val) {
                val = nums[i];
                idx = i;
            }
        }
        // 创建根节点
        TreeNode* root = new TreeNode(val);
        // 递归
        root->left = constructMaximumBinaryTreeHelper(nums, left, idx - 1);
        root->right = constructMaximumBinaryTreeHelper(nums, idx + 1, right);
        return root;
    }
};

【从前序与中序遍历序列构造二叉树】

给定两个整数数组 preorder 和 inorder ，其中 preorder 是二叉树的先序遍历， inorder 是同一棵树的中序遍历，请构造二叉树并返回其根节点。

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
class Solution {
   public:
    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
        // 通过先序遍历数组确定根的位置，然后通过中序遍历数组构造二叉树
        return buildTreeHelper(preorder, 0, preorder.size() - 1, inorder, 0,
                               inorder.size() - 1);
    }

    TreeNode* buildTreeHelper(vector<int>& preorder, int preleft, int preright,
                              vector<int>& inorder, int inleft, int inright) {
        if (preleft > preright || inleft > inright) return nullptr;
        // 通过先序遍历数组部分得到根节点
        int root_val = preorder[preleft];
        // 到中序遍历数组中找到根节点
        int idx;
        for (int i = inleft; i <= inright; i++) {
            if (inorder[i] == root_val) {
                idx = i;
                break;
            }
        }
        // 创建根节点
        TreeNode* root = new TreeNode(root_val);
        // 判断该根节点左右子树的结点数
        int left_nodes = idx - inleft;
        int right_nodes = inright - idx;
        // 递归
        root->left =
            buildTreeHelper(preorder, preleft + 1, (left_nodes + preleft),
                            inorder, inleft, idx - 1);
        root->right = buildTreeHelper(preorder, (left_nodes + preleft + 1),
                                      preright, inorder, idx + 1, inright);
        return root;
    }
};

【从中序与后序遍历序列构造二叉树】

给定两个整数数组 inorder 和 postorder ，其中 inorder 是二叉树的中序遍历， postorder 是同一棵树的后序遍历，请你构造并返回这颗 二叉树 。

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
class Solution {
   public:
    TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {
        return buildTreeHelper(inorder, 0, inorder.size() - 1, postorder, 0,
                               postorder.size() - 1);
    }

    TreeNode* buildTreeHelper(vector<int>& inorder, int inleft, int inright,
                              vector<int>& postorder, int postleft,
                              int postright) {
        if (inleft > inright) return nullptr;
        // 根据后序遍历数组找到根节点 最后一个就是根节点
        int root_val = postorder[postright];
        // 找到根节点在中序遍历数组中的位置
        int idx;
        for (int i = inleft; i <= inright; i++) {
            if (inorder[i] == root_val) {
                idx = i;
                break;
            }
        }
        // 创建根节点
        TreeNode* root = new TreeNode(root_val);
        // 确定左子树和右子树结点数量
        int left_nodes = idx - inleft;
        int right_nodes = inright - idx;
        // 递归
        root->left = buildTreeHelper(inorder, inleft, idx - 1, postorder,
                                     postleft, postright - right_nodes - 1);
        root->right = buildTreeHelper(inorder, idx + 1, inright, postorder,
                                      postleft + left_nodes - 1, postright - 1);
        return root;
    }
};

【总结】

这三道题都是关于如何构建二叉树的，而构建二叉树的关键在于【中序遍历数组】+【可以确定根节点的条件】

在【最大二叉树】中可以确定根节点的条件是最大元素，而在后两道题中分别是前序遍历数组和后序遍历数组。

（三）

寻找重复的子树 652

【寻找重复的子树】

给定一棵二叉树 root，返回所有重复的子树。

对于同一类的重复子树，你只需要返回其中任意一棵的根结点即可。

如果两棵树具有相同的结构和相同的结点值，则它们是重复的。

【思路】

要找重复的子树，【就需要记录之前的子树，然后再去匹配】

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
class Solution {
   private:
    unordered_map<string, int> memo; // 记录子树出现的次数 string表示树的结构 int表示出现次数
    vector<TreeNode*> res; // 结果集

   public:
    vector<TreeNode*> findDuplicateSubtrees(TreeNode* root) {
        findDuplicateSubtreesHelper(root);
        return res;
    }

    string findDuplicateSubtreesHelper(TreeNode* root) {
        if (root == nullptr) {
            return "#";
        }

        string left = findDuplicateSubtreesHelper(root->left);
        string right = findDuplicateSubtreesHelper(root->right);

        // 
        string tree = "";
        tree.append(left).append(",").append(right).append(",").append(
            to_string(root->val));

        if (memo.count(tree) && memo[tree] == 1) {
            res.push_back(root);
            memo[tree] = memo[tree] + 1;
        } else if (!memo[tree]) {
            memo[tree] = 1;
        }

        return tree;
    }
};

二叉树的序列化

  1. 二叉树的序列化与反序列化

使用Java

序列化是将一个数据结构或者对象转换为连续的比特位的操作，进而可以将转换后的数据存储在一个文件或者内存中，同时也可以通过网络传输到另一个计算机环境，采取相反方式重构得到原数据。

请设计一个算法来实现二叉树的序列化与反序列化。这里不限定你的序列 / 反序列化算法执行逻辑，你只需要保证一个二叉树可以被序列化为一个字符串并且将这个字符串反序列化为原始的树结构。

提示: 输入输出格式与 LeetCode 目前使用的方式一致，详情请参阅 LeetCode 序列化二叉树的格式。你并非必须采取这种方式，你也可以采用其他的方法解决这个问题。

这里提供四种方法（两种思路：递归和迭代）

每种方法的序列化过程都十分的简单，关键在于反序列化过程。

1、【前序遍历】/ 【后序遍历】：按理说，将二叉树序列化后再变回二叉树，是还需要中序遍历数组的。但是在序列化的时候，将空指针的也加入序列化的过程，也就是说二叉树序列化后可以是包含空指针，有了空指针的位置，就可以只依靠前序遍历或后序遍历重构二叉树。而前序遍历和后序遍历的区别就在于根节点的位置不同。【而这里的递归思路和之前不一样】，之前是找到序列中表示左子树的部分进行递归，...

2、【层次遍历】：利用队列对二叉树进行按层次遍历

3、【递归定义】

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
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
package algorithm.tree.binaryTree;

import algorithm.tree.TreeNode;
import sun.font.TextRecord;
import sun.reflect.generics.tree.Tree;

import javax.naming.directory.SearchResult;
import java.util.*;

/**
 * 二叉树的序列化
 */

public class Serialization {
    
    List<String> list;
    
    // 前序遍历
    
    private String preSerialize(TreeNode root){
        if(root == null) return "#";
        
        String left = preSerialize(root.left);
        String right = preSerialize(root.right);
    
        return root.val + "," + left + "," + right;
    }
    // 下面这个解法在某些情况下无法给出正确答案，虽然感觉它很正确
    // 这里采用的递归思路是: 找到data中属于左子树和右子树的部分，再去递归
    /*
    private TreeNode preDeserialize(String data){
        if(data == null || data.length() == 0) return null;
        
        char c = data.charAt(0);
        if(c == '#') return null;
        
        // 前序排列的第一个就是根节点
        TreeNode root = new TreeNode(c - '0');
        // 找到左子树的部分
        int left_tree_nodes = 1; // 无论root的左节点是空还是存在左子树 data[1]一定是属于左子树的
        int i = 1;
        while(left_tree_nodes > 0 && i < data.length()){
            if(data.charAt(i) != '#'){ // 如果存在非空结点，左子树在data中的元素个数多2个
                left_tree_nodes += 2;
            }
            left_tree_nodes--;
            i++;
        }
        root.left = preDeserialize(data.substring(1, i));
        // 找到右子树的部分
        root.right = preDeserialize(data.substring(i));
        return root;
    }
     */
    
    private TreeNode preDeserialize(String data){
        list = new ArrayList<>();
        Collections.addAll(list, data.split(","));
        return preDeserializeHelper();
    }
    
    private TreeNode preDeserializeHelper(){
        if(list.isEmpty()) return null;
        
        String rootVal = list.remove(0);
        if(rootVal.equals("#")) return null;
        TreeNode root = new TreeNode(Integer.parseInt(rootVal));
        
        root.left = preDeserializeHelper();
        root.right = preDeserializeHelper();
        
        return root;
    }
    
    // 后序遍历
    
    private String postSerialize(TreeNode root){
        if(root == null) return "#";
        
        String left = postSerialize(root.left);
        String right = postSerialize(root.right);
        
        return left + "," + right + "," + root.val;
    }
    
    private TreeNode postDeserialize(String data){
        list = new ArrayList<>();
        String[] split = data.split(",");
        for(int i = split.length - 1; i >= 0; i--){
            list.add(split[i]);
        }
        return postDeserializeHelper();
    }
    
    private TreeNode postDeserializeHelper(){
        if(list.isEmpty()) return null;
        
        String rootVal = list.remove(0);
        if(rootVal.equals("#")) return null;
        TreeNode root = new TreeNode(Integer.parseInt(rootVal));
        
        root.right = postDeserializeHelper();
        root.left = postDeserializeHelper();
        
        return root;
    }
    
    // 中序遍历
    
    private String inSerialize(TreeNode root){
        if(root == null) return "#";
    
        String left = postSerialize(root.left);
        String right = postSerialize(root.right);
    
        return left + "," + root.val + "," + right;
    }
    
    // 无法进行反序列化
    private TreeNode inDeserialize(String data){
        return null;
    }
    
    // 使用层级遍历
    
    private String levelSerialize(TreeNode root){
        if(root == null) return "";
        
        Queue<TreeNode> queue = new LinkedList<>();
        StringBuilder sb = new StringBuilder();
        
        queue.offer(root);
        while (!queue.isEmpty()){
            TreeNode node = queue.poll();
            
            if(node == null) sb.append("#");
            else {
                sb.append(node.val);
                queue.offer(node.left);
                queue.offer(node.right);
            }
            
            if (!queue.isEmpty()) sb.append(",");
        }
        
        return sb.toString();
    }
    
    private TreeNode levelDeserialize(String data){
        if(data.equals("")) return null; // 存在一个问题: split空字符串的时候返回的数组长度为1
        list = new ArrayList<>();
        Collections.addAll(list, data.split(","));
        return levelDeserializeHelper();
    }
    
    private TreeNode levelDeserializeHelper(){
        if(list.isEmpty()) return null;
        
        TreeNode root = new TreeNode(Integer.parseInt(list.remove(0))); // 根节点
        
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        
        while(!queue.isEmpty()){
            
            TreeNode node = queue.poll();
            
            String leftVal = list.remove(0);
            if(leftVal.equals("#")){
                node.left = null;
            } else {
                node.left = new TreeNode(Integer.parseInt(leftVal));
                queue.offer(node.left);
            }
            
            String rightVal = list.remove(0);
            if(rightVal.equals("#")){
                node.right = null;
            } else {
                node.right = new TreeNode(Integer.parseInt(rightVal));
                queue.offer(node.right);
            }
        }
        
        return root;
    }
    
    
    // Encodes a tree to a single string.
    public String serialize(TreeNode root) {
        return levelSerialize(root);
    }
    
    // Decodes your encoded data to tree.
    public TreeNode deserialize(String data) {
        return levelDeserialize(data);
    }
    
    public static void main(String[] args) {
        System.out.println("".split(",").length);
    }

}

class Codec {
    public String serialize(TreeNode root) {
        if (root == null) {
            return "X";
        }
        String left = "(" + serialize(root.left) + ")";
        String right = "(" + serialize(root.right) + ")";
        return left + root.val + right;
    }
    
    public TreeNode deserialize(String data) {
        int[] ptr = {0};
        return parse(data, ptr);
    }
    
    public TreeNode parse(String data, int[] ptr) {
        if (data.charAt(ptr[0]) == 'X') {
            ++ptr[0];
            return null;
        }
        TreeNode cur = new TreeNode(0);
        cur.left = parseSubtree(data, ptr);
        cur.val = parseInt(data, ptr);
        cur.right = parseSubtree(data, ptr);
        return cur;
    }
    
    public TreeNode parseSubtree(String data, int[] ptr) {
        ++ptr[0]; // 跳过左括号
        TreeNode subtree = parse(data, ptr);
        ++ptr[0]; // 跳过右括号
        return subtree;
    }
    
    public int parseInt(String data, int[] ptr) {
        int x = 0, sgn = 1;
        if (!Character.isDigit(data.charAt(ptr[0]))) {
            sgn = -1;
            ++ptr[0];
        }
        while (Character.isDigit(data.charAt(ptr[0]))) {
            x = x * 10 + data.charAt(ptr[0]++) - '0';
        }
        return x * sgn;
    }
}

利用后序遍历优化算法

二叉搜索子树的最大键值和 1373

给你一棵以 root 为根的 二叉树 ，请你返回 任意 二叉搜索子树的最大键值和。

【思路】

这道题无论是判断是否为BST，还是求树的键值和都需要用到左右子树的相关信息，而判断树是否为BST以及求树的键值和本身又是递归求解，一旦采用前序遍历的思想就是递归套递归，复杂度很高。原因就在于前面递归求过的到后面还得再递归再求一次，复杂度会达到指数级。、

而使用后序遍历的思想，可以在递归遍历的过程中直接拿到左右子树的相关信息，然后根据这些信息求出该树是否为BST以及键值和，依次向下求解，复杂度大大降低，只有线性复杂度。

还是要从大局看起，不要一开始就限于细节，应该再整体的递归布局想清楚后再考虑细节问题。否则不容易写出递归的解法。

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
public class Solution {
    
    final int NOT_BST = Integer.MIN_VALUE;
    int maxSum = 0;
    
    /**
     * 求二叉树中 键值和最大的二叉搜索子树
     */
    public int maxSumBST(TreeNode root){
        int res = maxSumBSTHelper(root);
        return maxSum;
    }
    
    /**
     * 
     * @param root 根节点
     * @return 如果是二叉树返回该树的键值和，如果不是则返回 NOT_BST
     */
    public int maxSumBSTHelper(TreeNode root) {
        if (root == null) return 0;
        
        int left = maxSumBSTHelper(root.left);
        int right = maxSumBSTHelper(root.right);
        
        if(left != NOT_BST && right != NOT_BST){ // 左右子树都是BST
            if(isBST(root)){ // 判断以root为根的树是否为BST
                int tree = left + root.val + right;
                if(tree > maxSum) maxSum = tree;
                return tree;
            } else {
                return NOT_BST;
            }
        } else { // 左子树或者右子树不是BST
            return NOT_BST;
        }
    }
    
    /**
     * 当该根节点的左右子树均为BST的前提下，判断以root为根的树是否为BST
     * @param root 根节点
     * @return 是否是BST
     */
    private boolean isBST(TreeNode root){
        if(root == null) return true;
        
        boolean is_left_satisfied = false; 
        boolean is_right_satisfied = false; 
        
        // 判断左子树是否满足条件
        TreeNode left = root.left;
        while (left != null && left.right != null){
            left = left.right;
        }
        if(left == null || left.val < root.val) is_left_satisfied = true;
        
        // 判断右子树是否满足条件
        TreeNode right = root.right;
        while (right != null && right.left != null){
            right = right.left;
        }
        if(right == null || right.val > root.val) is_right_satisfied = true;
        
        return is_left_satisfied & is_right_satisfied;
    }
    
    
}

总结

深入理解遍历方式

前中后序遍历

一般我们求解二叉树的前中后序遍历的框架如下

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
// 前序遍历框架
void preTraversal(TreeNode root){
    if(root == null) return;
    
    /* 处理 */
    
    preTraversal(root.left);
    preTraversal(root.right);
    
}

// 中序遍历框架
void inTraversal(TreeNode root){
    if(root == null) return;
    
    inTraversal(root.left);
    
    /* 处理 */
    
    inTraversal(root.right);
    
}

// 后序遍历框架
void postTraversal(TreeNode root){
    if(root == null) return;
    
    postTraversal(root.left);
    postTraversal(root.right);
    
    /* 处理 */
}

其实，用前中后序遍历的递归框架来解决问题，本质上就是【按照前中后序三种遍历顺序来处理每一个结点】，而利用这种框架来解决二叉树问题，只要考虑在每一个结点位置（/* 处理 */）应该编写怎样的逻辑。

层次遍历

1
2
3
4
5
6
7
8
9
10
11
void levelTraversal(TreeNode root){
    if(root == null) return;
    
    Queue<TreeNode> q = new LinkedList<>();
    q.offer(root);
    
    while(!q.isEmpty()){
        TreeNode node = q.poll();
        /* 处理 */
    }
}

两种解题思路

  • 遍历二叉树 =》 回溯算法思想
  • 分解问题 =》 动态规划思想

以【二叉树的最大深度】为例

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
// 分解问题: 将原问题分解为规模更小的子问题
public int maxDepth(TreeNode root) {
    if(root == null) return 0;
    int leftMax = maxDepth(root.left);
    int rightMax = maxDepth(root.right);
    return Math.max(leftMax, rightMax) + 1;
}

// 遍历二叉树
int depth = 0;
int res = 0;
public int maxDepth1(TreeNode root){
    traversal(root);
    return res;
}

private void traversal(TreeNode root){
    if(root == null){ // 到达分支的最底部
        res = Math.max(res, depth);
        return;
    }
    depth++; // 进入子树，深度+1
    traversal(root.left);
    traversal(root.right);
    depth--; // 回到根节点，深度-1
}

【二叉树的直径】

给定一棵二叉树，你需要计算它的直径长度。一棵二叉树的直径长度是任意两个结点路径长度中的最大值。这条路径可能穿过也可能不穿过根结点。

利用后序遍历的递归方法，得到左右子树中距离子树根节点的最大距离，由此计算经过root结点的最大距离，并更新diameter。

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
// 遍历二叉树
int diameter = 0;
public int diameterOfBinaryTree(TreeNode root) {
    if(root == null) return 0;
    diameterOfBinaryTreeHelper(root);
    return diameter;
}

/*
 *
 * @param root 根节点
 * @return 该树距离根节点的最远距离
 */
private int diameterOfBinaryTreeHelper(TreeNode root){
    if(root == null){
        return -1;
    }

    int left = diameterOfBinaryTreeHelper(root.left);
    int right = diameterOfBinaryTreeHelper(root.right);

    int distance_cross_root = left + right + 2;
    int max_distance_to_root = Math.max(left, right) + 1;

    diameter = Math.max(diameter, distance_cross_root);

    return max_distance_to_root;
}
leetcode刷题笔记
#leetcode
刷题笔记4-二叉树
http://example.com/2022/09/15/leetcode/刷题笔记4（二叉树）/
作者
zhc
发布于
2022年9月15日
许可协议