本节内容
- 530.二叉搜索树的最小绝对差
- 501.二叉搜索树中的众数
- 236. 二叉树的最近公共祖先
530.二叉搜索树的最小绝对差※
建议：需要领悟一下二叉树遍历上双指针操作，优先掌握递归
题目链接： https://leetcode.cn/problems/minimum-absolute-difference-in-bst/
文章讲解： https://programmercarl.com/0530.%E4%BA%8C%E5%8F%89%E6%90%9C%E7%B4%A2%E6%A0%91%E7%9A%84%E6%9C%80%E5%B0%8F%E7%BB%9D%E5%AF%B9%E5%B7%AE.html
视频讲解： https://www.bilibili.com/video/BV1DD4y11779
题目分析
示例 1：
1
2
| 输入：root = [4,2,6,1,3]
输出：1
|
示例 2：
1
2
| 输入：root = [1,0,48,null,null,12,49]
输出：1
|
方案一
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
| class Solution {
public int getMinimumDifference(TreeNode root) {
if (root.left == null && root.right == null) return Integer.MAX_VALUE;
int leftAbs = Integer.MAX_VALUE,
rightAbs = Integer.MAX_VALUE;
TreeNode nodeTempLeft = root.left,
nodeTempRight = root.right;
if (nodeTempLeft != null) {
int minimumDifferenceLeft = getMinimumDifference(nodeTempLeft);
while (nodeTempLeft.right != null) {
nodeTempLeft = nodeTempLeft.right;
}
leftAbs = Math.abs(root.val - nodeTempLeft.val);
leftAbs = Math.min(leftAbs, minimumDifferenceLeft);
}
if (nodeTempRight != null) {
int minimumDifferenceRight = getMinimumDifference(nodeTempRight);
while (nodeTempRight.left != null) {
nodeTempRight = nodeTempRight.left;
}
rightAbs = Math.abs(root.val - nodeTempRight.val);
rightAbs = Math.min(rightAbs, minimumDifferenceRight);
}
return Math.min(leftAbs, rightAbs);
}
}
|
结果
解答成功:
执行耗时:0 ms,击败了100.00% 的Java用户
内存消耗:41.8 MB,击败了69.74% 的Java用户
分析
时间复杂度：
O( n )
空间复杂度：
O( )
代码随想录
https://programmercarl.com/0530.%E4%BA%8C%E5%8F%89%E6%90%9C%E7%B4%A2%E6%A0%91%E7%9A%84%E6%9C%80%E5%B0%8F%E7%BB%9D%E5%AF%B9%E5%B7%AE.html
思路
题目中要求在二叉搜索树上任意两节点的差的绝对值的最小值。
注意是二叉搜索树，二叉搜索树可是有序的。
遇到在二叉搜索树上求什么最值啊，差值之类的，就把它想成在一个有序数组上求最值，求差值，这样就简单多了。
递归
那么二叉搜索树采用中序遍历，其实就是一个有序数组。
在一个有序数组上求两个数最小差值，这是不是就是一道送分题了。
最直观的想法，就是把二叉搜索树转换成有序数组，然后遍历一遍数组，就统计出来最小差值了。
代码如下：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
| class Solution {
private:
vector<int> vec;
void traversal(TreeNode* root) {
if (root == NULL) return;
traversal(root->left);
vec.push_back(root->val);
traversal(root->right);
}
public:
int getMinimumDifference(TreeNode* root) {
vec.clear();
traversal(root);
if (vec.size() < 2) return 0;
int result = INT_MAX;
for (int i = 1; i < vec.size(); i++) {
result = min(result, vec[i] - vec[i-1]);
}
return result;
}
};
|
以上代码是把二叉搜索树转化为有序数组了，其实在二叉搜素树中序遍历的过程中，我们就可以直接计算了。
需要用一个pre节点记录一下cur节点的前一个节点。
如图：
一些同学不知道在递归中如何记录前一个节点的指针，其实实现起来是很简单的，大家只要看过一次，写过一次，就掌握了。
代码如下：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
| class Solution {
private:
int result = INT_MAX;
TreeNode* pre = NULL;
void traversal(TreeNode* cur) {
if (cur == NULL) return;
traversal(cur->left);
if (pre != NULL){
result = min(result, cur->val - pre->val);
}
pre = cur;
traversal(cur->right);
}
public:
int getMinimumDifference(TreeNode* root) {
traversal(root);
return result;
}
};
|
代码实现
递归
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
| class Solution {
TreeNode pre;
int result = Integer.MAX_VALUE;
public int getMinimumDifference(TreeNode root) {
if(root==null)return 0;
traversal(root);
return result;
}
public void traversal(TreeNode root){
if(root==null)return;
traversal(root.left);
if(pre!=null){
result = Math.min(result,root.val-pre.val);
}
pre = root;
traversal(root.right);
}
}
|
迭代
中序遍历的迭代法
代码实现
統一迭代法-中序遍历
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
| class Solution {
public int getMinimumDifference(TreeNode root) {
Stack<TreeNode> stack = new Stack<>();
TreeNode pre = null;
int result = Integer.MAX_VALUE;
if(root != null)
stack.add(root);
while(!stack.isEmpty()){
TreeNode curr = stack.peek();
if(curr != null){
stack.pop();
if(curr.right != null)
stack.add(curr.right);
stack.add(curr);
stack.add(null);
if(curr.left != null)
stack.add(curr.left);
}else{
stack.pop();
TreeNode temp = stack.pop();
if(pre != null)
result = Math.min(result, temp.val - pre.val);
pre = temp;
}
}
return result;
}
}
|
迭代法-中序遍历
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 {
TreeNode pre;
Stack<TreeNode> stack;
public int getMinimumDifference(TreeNode root) {
if (root == null) return 0;
stack = new Stack<>();
TreeNode cur = root;
int result = Integer.MAX_VALUE;
while (cur != null || !stack.isEmpty()) {
if (cur != null) {
stack.push(cur);
cur = cur.left;
}else {
cur = stack.pop();
if (pre != null) {
result = Math.min(result, cur.val - pre.val);
}
pre = cur;
cur = cur.right;
}
}
return result;
}
}
|
501.二叉搜索树中的众数※
建议：和 530差不多双指针思路，不过 这里涉及到一个很巧妙的代码技巧。
题目链接： https://leetcode.cn/problems/find-mode-in-binary-search-tree/
文章讲解： https://programmercarl.com/0501.%E4%BA%8C%E5%8F%89%E6%90%9C%E7%B4%A2%E6%A0%91%E4%B8%AD%E7%9A%84%E4%BC%97%E6%95%B0.html
视频讲解： https://www.bilibili.com/video/BV1fD4y117gp
题目分析
示例 1：
1
2
| 输入：root = [1,null,2,2]
输出：[2]
|
示例 2：
方案一
递归的向hashMap中放数据，然后对hashMap进行排序
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
| class Solution {
Map<Integer, Integer> resultMap = new HashMap<>();
public int[] findMode(TreeNode root) {
recursion(root);
int max = Integer.MIN_VALUE;
List<Integer> resultList = new ArrayList<>();
for (Map.Entry<Integer, Integer> entry : resultMap.entrySet()) {
if (max < entry.getValue()) {
max = entry.getValue();
resultList = new ArrayList<>();
resultList.add(entry.getKey());
} else if (max == entry.getValue()) {
resultList.add(entry.getKey());
}
}
int[] result = new int[resultList.size()];
for (int i = 0; i < result.length; i++) {
result[i] = resultList.get(i);
}
return result;
}
private void recursion(TreeNode root) {
if (root == null) return;
resultMap.put(root.val, resultMap.getOrDefault(root.val, 0) + 1);
recursion(root.left);
recursion(root.right);
}
}
|
结果
解答成功:
执行耗时:4 ms,击败了31.45% 的Java用户
内存消耗:43.1 MB,击败了13.02% 的Java用户
分析
时间复杂度：
O( n )
代码随想录
https://programmercarl.com/0501.%E4%BA%8C%E5%8F%89%E6%90%9C%E7%B4%A2%E6%A0%91%E4%B8%AD%E7%9A%84%E4%BC%97%E6%95%B0.html
思路
首先如果不是二叉搜索树的话，应该怎么解题，是二叉搜索树，又应该如何解题，两种方式做一个比较，可以加深大家对二叉树的理解。
递归法
如果不是二叉搜索树
如果不是二叉搜索树，最直观的方法一定是把这个树都遍历了，用map统计频率，把频率排个序，最后取前面高频的元素的集合。
具体步骤如下：
- 这个树都遍历了，用map统计频率
至于用前中后序哪种遍历也不重要，因为就是要全遍历一遍，怎么个遍历法都行，层序遍历都没毛病！
这里采用前序遍历，代码如下：
1
2
3
4
5
6
7
8
|
void searchBST(TreeNode* cur, unordered_map<int, int>& map) {
if (cur == NULL) return ;
map[cur->val]++;
searchBST(cur->left, map);
searchBST(cur->right, map);
return ;
}
|
- 把统计的出来的出现频率（即map中的value）排个序
有的同学可能可以想直接对map中的value排序，还真做不到，C++中如果使用std::map或者std::multimap可以对key排序，但不能对value排序。
所以要把map转化数组即vector，再进行排序，当然vector里面放的也是pair<int, int>类型的数据，第一个int为元素，第二个int为出现频率。
代码如下：
1
2
3
4
5
6
| bool static cmp (const pair<int, int>& a, const pair<int, int>& b) {
return a.second > b.second;
}
vector<pair<int, int>> vec(map.begin(), map.end());
sort(vec.begin(), vec.end(), cmp);
|
- 取前面高频的元素
此时数组vector中已经是存放着按照频率排好序的pair，那么把前面高频的元素取出来就可以了。
代码如下：
1
2
3
4
5
6
7
| result.push_back(vec[0].first);
for (int i = 1; i < vec.size(); i++) {
if (vec[i].second == vec[0].second) result.push_back(vec[i].first);
else break;
}
return result;
|
是二叉搜索树
既然是搜索树，它中序遍历就是有序的。
如图：
中序遍历代码如下：
1
2
3
4
5
6
7
| void searchBST(TreeNode* cur) {
if (cur == NULL) return ;
searchBST(cur->left);
（处理节点）
searchBST(cur->right);
return ;
}
|
遍历有序数组的元素出现频率，从头遍历，那么一定是相邻两个元素作比较，然后就把出现频率最高的元素输出就可以了。
关键是在有序数组上的话，好搞，在树上怎么搞呢？
这就考察对树的操作了。
弄一个指针指向前一个节点，这样每次cur（当前节点）才能和pre（前一个节点）作比较。
而且初始化的时候pre = NULL，这样当pre为NULL时候，我们就知道这是比较的第一个元素。
代码如下：
1
2
3
4
5
6
7
8
| if (pre == NULL) {
count = 1;
} else if (pre->val == cur->val) {
count++;
} else {
count = 1;
}
pre = cur;
|
此时又有问题了，因为要求最大频率的元素集合（注意是集合，不是一个元素，可以有多个众数），如果是数组上大家一般怎么办？
应该是先遍历一遍数组，找出最大频率（maxCount），然后再重新遍历一遍数组把出现频率为maxCount的元素放进集合。（因为众数有多个）
这种方式遍历了两遍数组。
那么我们遍历两遍二叉搜索树，把众数集合算出来也是可以的。
但这里其实只需要遍历一次就可以找到所有的众数。
那么如何只遍历一遍呢？
如果 频率count 等于 maxCount（最大频率），当然要把这个元素加入到结果集中（以下代码为result数组），代码如下：
1
2
3
| if (count == maxCount) {
result.push_back(cur->val);
}
|
是不是感觉这里有问题，result怎么能轻易就把元素放进去了呢，万一，这个maxCount此时还不是真正最大频率呢。
所以下面要做如下操作：
频率count 大于 maxCount的时候，不仅要更新maxCount，而且要清空结果集（以下代码为result数组），因为结果集之前的元素都失效了。
1
2
3
4
5
| if (count > maxCount) {
maxCount = count;
result.clear();
result.push_back(cur->val);
}
|
代码实现
暴力法
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
| class Solution {
public int[] findMode(TreeNode root) {
Map<Integer, Integer> map = new HashMap<>();
List<Integer> list = new ArrayList<>();
if (root == null) return list.stream().mapToInt(Integer::intValue).toArray();
searchBST(root, map);
List<Map.Entry<Integer, Integer>> mapList = map.entrySet().stream()
.sorted((c1, c2) -> c2.getValue().compareTo(c1.getValue()))
.collect(Collectors.toList());
list.add(mapList.get(0).getKey());
for (int i = 1; i < mapList.size(); i++) {
if (mapList.get(i).getValue() == mapList.get(i - 1).getValue()) {
list.add(mapList.get(i).getKey());
} else {
break;
}
}
return list.stream().mapToInt(Integer::intValue).toArray();
}
void searchBST(TreeNode curr, Map<Integer, Integer> map) {
if (curr == null) return;
map.put(curr.val, map.getOrDefault(curr.val, 0) + 1);
searchBST(curr.left, map);
searchBST(curr.right, map);
}
}
|
中序遍历-不使用额外空间，利用二叉搜索树特性
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
| class Solution {
ArrayList<Integer> resList;
int maxCount;
int count;
TreeNode pre;
public int[] findMode(TreeNode root) {
resList = new ArrayList<>();
maxCount = 0;
count = 0;
pre = null;
findMode1(root);
int[] res = new int[resList.size()];
for (int i = 0; i < resList.size(); i++) {
res[i] = resList.get(i);
}
return res;
}
public void findMode1(TreeNode root) {
if (root == null) {
return;
}
findMode1(root.left);
int rootValue = root.val;
if (pre == null || rootValue != pre.val) {
count = 1;
} else {
count++;
}
if (count > maxCount) {
resList.clear();
resList.add(rootValue);
maxCount = count;
} else if (count == maxCount) {
resList.add(rootValue);
}
pre = root;
findMode1(root.right);
}
}
|
迭代法
只要把中序遍历转成迭代，中间节点的处理逻辑完全一样。
代码实现
迭代法
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 int[] findMode(TreeNode root) {
TreeNode pre = null;
Stack<TreeNode> stack = new Stack<>();
List<Integer> result = new ArrayList<>();
int maxCount = 0;
int count = 0;
TreeNode cur = root;
while (cur != null || !stack.isEmpty()) {
if (cur != null) {
stack.push(cur);
cur =cur.left;
}else {
cur = stack.pop();
if (pre == null || cur.val != pre.val) {
count = 1;
}else {
count++;
}
if (count > maxCount) {
maxCount = count;
result.clear();
result.add(cur.val);
}else if (count == maxCount) {
result.add(cur.val);
}
pre = cur;
cur = cur.right;
}
}
return result.stream().mapToInt(Integer::intValue).toArray();
}
}
|
统一迭代法
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
| class Solution {
public int[] findMode(TreeNode root) {
int count = 0;
int maxCount = 0;
TreeNode pre = null;
LinkedList<Integer> res = new LinkedList<>();
Stack<TreeNode> stack = new Stack<>();
if(root != null)
stack.add(root);
while(!stack.isEmpty()){
TreeNode curr = stack.peek();
if(curr != null){
stack.pop();
if(curr.right != null)
stack.add(curr.right);
stack.add(curr);
stack.add(null);
if(curr.left != null)
stack.add(curr.left);
}else{
stack.pop();
TreeNode temp = stack.pop();
if(pre == null)
count = 1;
else if(pre != null && pre.val == temp.val)
count++;
else
count = 1;
pre = temp;
if(count == maxCount)
res.add(temp.val);
if(count > maxCount){
maxCount = count;
res.clear();
res.add(temp.val);
}
}
}
int[] result = new int[res.size()];
int i = 0;
for (int x : res){
result[i] = x;
i++;
}
return result;
}
}
|
236. 二叉树的最近公共祖先※
建议：本题其实是比较难的，可以先看我的视频讲解
题目链接： https://leetcode.cn/problems/lowest-common-ancestor-of-a-binary-tree/
文章讲解： https://programmercarl.com/0236.%E4%BA%8C%E5%8F%89%E6%A0%91%E7%9A%84%E6%9C%80%E8%BF%91%E5%85%AC%E5%85%B1%E7%A5%96%E5%85%88.html
视频讲解： https://www.bilibili.com/video/BV1jd4y1B7E2
题目分析
方案一：两次迭代遍历，
一个迭代用于判断此点是否符合祖节点的需求
一个迭代用于遍历二叉树
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 lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
if (root == null) return null;
TreeNode treeNodeLeft = lowestCommonAncestor(root.left, p, q);
TreeNode treeNodeRight = lowestCommonAncestor(root.right, p, q);
if (treeNodeLeft == null && treeNodeRight == null ) {
SUM = 0;
if (isRootNode(root, p, q))
return root;
return null;
}
if (treeNodeLeft != null){
return treeNodeLeft;
}
return treeNodeRight;
}
private int SUM = 0;
private boolean isRootNode(TreeNode root, TreeNode p, TreeNode q) {
if (root == null) return false;
if (root.val == p.val || root.val == q.val) SUM++;
boolean rootNodeLeft = isRootNode(root.left, p, q);
boolean rootNodeRight = isRootNode(root.right, p, q);
if (SUM == 2)
return true;
return false;
}
}
|
结果
解答成功:
执行耗时:6 ms,击败了99.83% 的Java用户
内存消耗:42.2 MB,击败了88.10% 的Java用户
分析
时间复杂度：
O( n ^ 2 )
代码随想录
https://programmercarl.com/0236.%E4%BA%8C%E5%8F%89%E6%A0%91%E7%9A%84%E6%9C%80%E8%BF%91%E5%85%AC%E5%85%B1%E7%A5%96%E5%85%88.html
思路
遇到这个题目首先想的是要是能自底向上查找就好了，这样就可以找到公共祖先了。
那么二叉树如何可以自底向上查找呢？
回溯啊，二叉树回溯的过程就是从低到上。
后序遍历（左右中）就是天然的回溯过程，可以根据左右子树的返回值，来处理中节点的逻辑。
接下来就看如何判断一个节点是节点q和节点p的公共祖先呢。
首先最容易想到的一个情况：如果找到一个节点，发现左子树出现结点p，右子树出现节点q，或者 左子树出现结点q，右子树出现节点p，那么该节点就是节点p和q的最近公共祖先。 即情况一：
判断逻辑是 如果递归遍历遇到q，就将q返回，遇到p 就将p返回，那么如果 左右子树的返回值都不为空，说明此时的中节点，一定是q 和p 的最近祖先。
那么有录友可能疑惑，会不会左子树 遇到q 返回，右子树也遇到q返回，这样并没有找到 q 和p的最近祖先。
这么想的录友，要审题了，题目强调：二叉树节点数值是不重复的，而且一定存在 q 和 p。
但是很多人容易忽略一个情况，就是节点本身p(q)，它拥有一个子孙节点q(p)。 情况二：
其实情况一 和 情况二 代码实现过程都是一样的，也可以说，实现情况一的逻辑，顺便包含了情况二。
因为遇到 q 或者 p 就返回，这样也包含了 q 或者 p 本身就是 公共祖先的情况。
递归三部曲：
需要递归函数返回值，来告诉我们是否找到节点q或者p，那么返回值为bool类型就可以了。
但我们还要返回最近公共节点，可以利用上题目中返回值是TreeNode * ，那么如果遇到p或者q，就把q或者p返回，返回值不为空，就说明找到了q或者p。
代码如下：
1
| TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q)
|
遇到空的话，因为树都是空了，所以返回空。
那么我们来说一说，如果 root == q，或者 root == p，说明找到 q p ，则将其返回，这个返回值，后面在中节点的处理过程中会用到，那么中节点的处理逻辑，下面讲解。
代码如下：
1
| if (root == q || root == p || root == NULL) return root;
|
值得注意的是 本题函数有返回值，是因为回溯的过程需要递归函数的返回值做判断，但本题我们依然要遍历树的所有节点。
递归函数有返回值就是要遍历某一条边，但有返回值也要看如何处理返回值！
如果递归函数有返回值，如何区分要搜索一条边，还是搜索整个树呢？
搜索一条边的写法：
1
2
3
| if (递归函数(root->left)) return ;
if (递归函数(root->right)) return ;
|
搜索整个树写法：
1
2
3
| left = 递归函数(root->left);
right = 递归函数(root->right);
left与right的逻辑处理;
|
看出区别了没？
在递归函数有返回值的情况下：如果要搜索一条边，递归函数返回值不为空的时候，立刻返回，如果搜索整个树，直接用一个变量left、right接住返回值，这个left、right后序还有逻辑处理的需要，也就是后序遍历中处理中间节点的逻辑（也是回溯）。
那么为什么要遍历整棵树呢？直观上来看，找到最近公共祖先，直接一路返回就可以了。
如图：
就像图中一样直接返回7，多美滋滋。
但事实上还要遍历根节点右子树（即使此时已经找到了目标节点了），也就是图中的节点4、15、20。
因为在如下代码的后序遍历中，如果想利用left和right做逻辑处理， 不能立刻返回，而是要等left与right逻辑处理完之后才能返回。
1
2
3
| left = 递归函数(root->left);
right = 递归函数(root->right);
left与right的逻辑处理;
|
所以此时大家要知道我们要遍历整棵树。知道这一点，对本题就有一定深度的理解了。
那么先用left和right接住左子树和右子树的返回值，代码如下：
1
2
3
| TreeNode* left = lowestCommonAncestor(root->left, p, q);
TreeNode* right = lowestCommonAncestor(root->right, p, q);
|
如果left 和 right都不为空，说明此时root就是最近公共节点。这个比较好理解
如果left为空，right不为空，就返回right，说明目标节点是通过right返回的，反之依然。
这里有的同学就理解不了了，为什么left为空，right不为空，目标节点通过right返回呢？
如图：
图中节点10的左子树返回null，右子树返回目标值7，那么此时节点10的处理逻辑就是把右子树的返回值（最近公共祖先7）返回上去！
这里也很重要，可能刷过这道题目的同学，都不清楚结果究竟是如何从底层一层一层传到头结点的。
那么如果left和right都为空，则返回left或者right都是可以的，也就是返回空。
代码如下：
1
2
3
4
5
6
| if (left == NULL && right != NULL) return right;
else if (left != NULL && right == NULL) return left;
else {
return NULL;
}
|
那么寻找最小公共祖先，完整流程图如下：
从图中，大家可以看到，我们是如何回溯遍历整棵二叉树，将结果返回给头结点的！
代码实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
| class Solution {
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
if (root == null || root == p || root == q) {
return root;
}
TreeNode left = lowestCommonAncestor(root.left, p, q);
TreeNode right = lowestCommonAncestor(root.right, p, q);
if(left == null && right == null) {
return null;
}else if(left == null && right != null) {
return right;
}else if(left != null && right == null) {
return left;
}else {
return root;
}
}
}
|