每日算法之二叉树的下一个结点

JZ8二叉树的下一个结点

描述

1. 给定一个二叉树其中的一个结点，请找出中序遍历顺序的下一个结点并且返回。注意，树中的结点不仅包含左右子结点，同时包含指向父结点的next指针。
3. 示例:
4. 输入:{8,6,10,5,7,9,11},8
5. 返回:9
6. 解析:这个组装传入的子树根节点，其实就是整颗树，中序遍历{5,6,7,8,9,10,11}，根节点8的下一个节点就是9，应该返回{9,10,11}，后台只打印子树的下一个节点，所以只会打印9

复制代码

具体做法：

1. step 1：首先先根据当前给出的结点找到根节点
2. step 2：然后根节点调用中序遍历
3. step 3：将中序遍历结果存储下来
4. step 4：最终拿当前结点匹配是否有符合要求的下一个结点

复制代码

代码

1. package mid.JZ8二叉树的下一个结点;
3. import java.util.ArrayList;
5. class TreeLinkNode {
6.     int val;
7.     TreeLinkNode left = null;
8.     TreeLinkNode right = null;
9.     TreeLinkNode next = null;
11.     TreeLinkNode(int val) {
12.         this.val = val;
13.     }
14. }
16. public class Solution {
17.     ArrayList<TreeLinkNode> nodes = new ArrayList<>();
19.     public TreeLinkNode GetNext(TreeLinkNode pNode) {
21.         TreeLinkNode root = pNode;
22.         //获取根节点
23.         while (root.next != null) root = root.next;
25.         //获取中序遍历集合
26.         inOrder(root);
28.         //匹配
29.         for (int i = 0; i < nodes.size() - 1; i++) {
30.             if (pNode.val == nodes.get(i).val) {
31.                 return nodes.get(i + 1);
32.             }
33.         }
34.         return null;
35.     }
37.     public void inOrder(TreeLinkNode root) {
38.         if (root != null) {
39.             inOrder(root.left);
40.             nodes.add(root);
41.             inOrder(root.right);
42.         }
43.     }
44. }

复制代码