题解 | #二叉树的下一个结点#
二叉树的下一个结点
https://www.nowcoder.com/practice/9023a0c988684a53960365b889ceaf5e
解答：首先如果此题没有空间复杂度要求那就是简单题，思考不用数组的方法，首先输入的不是根结点，而是目标结点，所以第一步得通过next，找到该树的根结点，找根结点之前得把目标结点的val保存到target；然后通过中序遍历开始访问，逻辑写在中间即中序遍历，我们通过一个flag标志来解决先后关系，首先如果root.val==target，即找到目标结点，我们要输出的就是它的下一个结点，此时将flag由0改为1，则到下一个结点时flag==1，则找到输出点，然后重新把flag改为0。时间复杂度分析，其中找根结点为O(n)，遍历所有结点为O(n)，所以综合时间复杂度为O(n),空间复杂度为O(1)。
class Solution {
public:
//全局变量
TreeLinkNode* res;
int flag=0;
TreeLinkNode* GetNext(TreeLinkNode* pNode) {
//输入为空
if(pNode==NULL)return NULL;
int target=pNode->val;
//找到此树的根结点
while(pNode->next!=NULL){
pNode=pNode->next;
}
//传入根结点和目标值
dfs(pNode,target);
return res;
}
void dfs(TreeLinkNode* root,int tar){
if(root==NULL)return;
dfs(root->left,tar);
//中序遍历
//标志为1，代表上一个结点为target
if(flag==1){
res=root;
flag=0;
}
//找到target，将标志改为1
if(root->val==tar){
flag=1;
}
dfs(root->right,tar);
}
};
查看20道真题和解析
投递TCL等公司10个岗位 >
