【牛客 - 剑指offer】JZ8 二叉树的下一个结点 Java实现

对于没有找到的，会在for循环结束以后，返回null

修改的代码

int size = inOrderNodes.size();
for (int i = 0; i < size - 1; i++) {
    if (inOrderNodes.get(i) == targetNode) {
        return inOrderNodes.get(i + 1);
    }
}
return null;
1
2
3
4
5
6
7

完整的代码

import java.util.*;

/*
public class TreeLinkNode {
    int val;
    TreeLinkNode left = null;
    TreeLinkNode right = null;
    TreeLinkNode next = null;

    TreeLinkNode(int val) {
        this.val = val;
    }
}
*/
public class Solution {

    private ArrayList<TreeLinkNode> inOrderNodes = new ArrayList<>();

    public TreeLinkNode GetNext(TreeLinkNode pNode) {

        TreeLinkNode targetNode = pNode;
        while (pNode.next != null) {
            pNode = pNode.next;
        }

        inOrderSearch(pNode);

		int size = inOrderNodes.size();
		for (int i = 0; i < size - 1; i++) {
		    if (inOrderNodes.get(i) == targetNode) {
		        return inOrderNodes.get(i + 1);
		    }
		}
		return null;
    }

    private void inOrderSearch(TreeLinkNode pNode) {
        if (pNode == null) {
            return;
        }
        inOrderSearch(pNode.left);
        inOrderNodes.add(pNode);
        inOrderSearch(pNode.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
36
37
38
39
40
41
42
43
44
45
46

方案二 分类直接寻找（分情况讨论）

思路

1. 如果给出的节点有右子节点，则最终要返回的下一个节点即右子树的最左下的节点

注意不是该节点的右节点，因为可能会出现右节点又是一棵子树的情况，所以要不断深入到右子树最左下的节点

2. 如果给出的节点无右子节点

   • 判断该节点是否有父节点

     • 没有父节点

       • 则该节点就是中序遍历的最后一个节点，返回null

     • 有父节点

       • 且是当前节点是其父节点的左子节点，则返回其父节点

       • 且是当前节点是其父节点的右子节点，则先要沿着左上方父节点爬树，一直爬到当前节点是其父节点的左子节点为止，返回的就是这个父节点；如果没有满足条件的节点，则返回NULL

代码（版本一）

根据上面的思路，写的代码

import java.util.*;

/*
public class TreeLinkNode {
    int val;
    TreeLinkNode left = null;
    TreeLinkNode right = null;
    TreeLinkNode next = null;

    TreeLinkNode(int val) {
        this.val = val;
    }
}
*/
public class Solution {
    public TreeLinkNode GetNext(TreeLinkNode pNode) {

        //有右子节点
        if (pNode.right != null) {
            pNode = pNode.right;
            while (pNode.left != null) {
                pNode = pNode.left;
            }
            return pNode;
        } else {
            //无右子节点
            //判断是否有父节点
            //没有父节点，也没有右子节点
            if (pNode.next == null) {
                return null;
            } else {
                //有父节点
                //判断是否是其父节点的左子节点
                if (pNode.next.left == pNode) {
                    return pNode.next;
                } else {
                	//不是该父节点的左子节点，即是该父节点的右子节点
                    while (pNode.next != null && pNode.next.left != pNode) {
                        pNode = pNode.next;
                    }
                    if (pNode.next == null) {
                        return null;
                    }
                    return pNode.next;
                }
            }
        }
    }
}
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

代码（版本二）

根绝官方给的代码，把上面的代码修改了一下，更简洁一些

import java.util.*;

public class Solution {
    public TreeLinkNode GetNext(TreeLinkNode pNode) {
        // 情况一
        if (pNode.right != null) {
            pNode = pNode.right;
            // 一直找到右子树的最左下的结点为返回值
            while (pNode.left != null) {
                pNode = pNode.left;
            }
            return pNode;
        }

        // 情况二
        //该节点的父节点不为空，且该节点是父节点的左子节点
        if (pNode.next != null && pNode.next.left == pNode) {
            return pNode.next;
        }

        // 情况三
        //该节点的父节点不为空，且该节点是父节点的右子节点
        // 沿着左上一直爬树，爬到当前结点是其父节点的左自己结点为止
        while (pNode.next != null && pNode.next.left != pNode) {
            pNode = pNode.next;
        }
        if (pNode.next == null) {
            return null;
        }
        return pNode.next;
    }
}
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