本文包含的题目有:
94. Binary Tree Inorder Traversal
95. Unique Binary Search Trees II
96. Unique Binary Search Trees
98. Validate Binary Search Tree
99. Recover Binary Search Tree
100. Same Tree
101. Symmetric Tree
102. Binary Tree Level Order Traversal
103. Binary Tree Zigzag Level Order Traversal
104. Maximum Depth of Binary Tree
105. Construct Binary Tree from Preorder and Inorder Traversal
106. Construct Binary Tree from Inorder and Postorder Traversal
107. Binary Tree Level Order Traversal II
108. Convert Sorted Array to Binary Search Tree
110. Balanced Binary Tree
111. Minimum Depth of Binary Tree
112. Path Sum
113. Path Sum II
437. Path Sum III
94. Binary Tree Inorder Traversal
解题思路
- 二叉树的中序遍历;
代码
1 | class Solution |
95. Unique Binary Search Trees II
解题思路
- 使用分治的方法解决;
代码
1 | class Solution |
96. Unique Binary Search Trees
解题思路I
- 使用DP动态规划,每添加一个新节点,首先保持已有的树结构不变,则新节点只有两个位置可以放置,从而有:
res[i] += res[i-1] * 2
;- 如果将已有的树结构拆开,则只能拆成两个部分,前一部分的右子节点为新节点,新节点的左子节点为右半部分,从而有:
res[i] += res[j] * res[i-j-1]
;
代码
1 | class Solution |
解题思路II
- 继续延续上述DP的思路,将
res[i-1] * 2
转变为res[0] * res[i-1]
+res[i-1] * res[0]
,然后更新原来的代码,更加简洁;
代码
1 | class Solution |
98. Validate Binary Search Tree
解题思路
- 仍然是使用中序遍历,维持一个pre变量,确保每一个
cur > pre
即可;
代码
1 | class Solution |
99. Recover Binary Search Tree
解题思路
- 仍然是中序遍历,遍历一遍,找出乱序的两个节点即可;
代码
1 | class Solution |
100. Same Tree
解题思路
- 这道题就迭代去比较就可以了, 注意两个都是
NULL
的情况;
代码
1 | class Solution |
101. Symmetric Tree
解题思路
- 按照对称的位置去比较;
代码
1 | class Solution |
102. Binary Tree Level Order Traversal
解题思路
- 使用一个
queue
进行广度优先搜索;
代码
1 | class Solution |
103. Binary Tree Zigzag Level Order Traversal
解题思路
- 仍然按照上述思路进行,使用一个
queue
保存每一层的数据,这里注意在偶数层进行翻转即可;
代码
1 | class Solution |
104. Maximum Depth of Binary Tree
解题思路
- 使用一个递归来解决;
代码
1 | class Solution |
105. Construct Binary Tree from Preorder and Inorder Traversal
解题思路
- 由中序遍历和先序遍历来构建树结构;
代码
1 | class Solution |
106. Construct Binary Tree from Inorder and Postorder Traversal
解题思路
- 中序遍历和后序遍历构建树结构,使用
unordered_map
进行辅助存储;
代码
1 | class Solution |
107. Binary Tree Level Order Traversal II
解题思路
- 跟之前的题目一样,最后进行一下翻转就可以了;
代码
1 | class Solution |
108. Convert Sorted Array to Binary Search Tree
解题思路
- 使用分治的思想去构建,每次首先构建中间节点即可;
代码
1 | class Solution { |
110. Balanced Binary Tree
解题思路I
- 遍历每一个节点,检查是否平衡;
代码
1 | class Solution |
解题思路II
- 使用DFS进行深度搜索,每次搜索返回树的高度,如果平衡就返回实际高度值,否则返回
-1
,最后进行判断即可;
代码
1 | class Solution |
111. Minimum Depth of Binary Tree
解题思路
- 简单题,但是有点小麻烦,弄清楚边界问题,只有
!root->left && !root->right
才可以结束遍历,有一个子节点不为NULL
就需要继续计算,两个均不为NULL
则取较小的一个;
代码
1 | class Solution |
112. Path Sum
解题思路
- 遍历每一条路径,检查是否有符合要求的结果;
- 注意这里需要判断左右子树是不是为
NULL
,即当前节点是不是叶子节点,然后分情况进行讨论;
代码
1 | class Solution |
113. Path Sum II
解题思路
- 采用递归和回溯的方式,遍历各个分支,如果符合要求就保存;
代码
1 | class Solution |
437. Path Sum III
解题思路
- 确定一个起始点,然后检查以该起始点开始有多少个分支符合要求,最后进行累加;
- 确定起点之后,只能在后面一直追加,如果已经计算得到了所求的sum值,在其后继续追加节点,如果追加节点的和为0的话也满足要求,此时计数继续加一;
代码
1 | class Solution |