题解 | #二叉树的下一个结点#

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

TreeLinkNode(int val) {
    this.val = val;
}

} */ import java.util.LinkedList; import java.util.List;

public class Solution { List list = new LinkedList<>();

public TreeLinkNode GetNext(TreeLinkNode pNode) {
    if(pNode == null) return null;

//如果只有一个结点，返回空 if(pNode.left==null && pNode.right==null && pNode.next==null) return null;

//寻找对应的根节点 TreeLinkNode root = findRoot(pNode); dfs(root);//将树的中序遍历放入链表中 for(int i = 0;i < list.size();i++) { if(i == 0) { list.get(0).right = list.get(1); continue; } if(i == list.size() - 1) { list.get(i).left = list.get(i-1); continue; }

    	list.get(i).left = list.get(i-1);
    	list.get(i).right = list.get(i+1);
    }
    
    TreeLinkNode newNode = new TreeLinkNode(-10);
    //在链表中寻找对应值
    for (TreeLinkNode treeNode : list) {
		if(treeNode.val == pNode.val){
            if(treeNode.right != null) newNode.val = treeNode.right.val;
			else return null;
        }
	}
	
	return newNode;
}

public void dfs(TreeLinkNode tree) {
	if(tree == null) return;
	
	dfs(tree.left);
	list.add(tree);
	dfs(tree.right);
}

public TreeLinkNode findRoot(TreeLinkNode node) {
	while(node.next != null) node = node.next;
	return node;
}

}