题解 | JZ8 二叉树的下一个结点
因为是要找到给定数据中序遍历的下一个值。所以我们要把重点放在中序遍历上。
所以需要单独一个模块来做中序遍历这件事。
而在使用中序遍历前，我们首先需要知道根节点是什么，利用给的pNode节点不断向上找，找到最顶上为止即为根节点，用根节点来做中序遍历。
我们设置flag和ans两个变量。flag表示是否遍历到了target数据，而ans表示最终的返回值。因为要找到target的下一个对象，所以当满足了flag为true之后的下一个对象就是我们要找的数据。所以直接看ans是否已经有值，如果没有值，那么这就是target的下一个数据。
/*
struct TreeLinkNode {
int val;
struct TreeLinkNode *left;
struct TreeLinkNode *right;
struct TreeLinkNode *next;
TreeLinkNode(int x) :val(x), left(NULL), right(NULL), next(NULL) {
}
};
*/
class Solution {
public:
bool flag;
TreeLinkNode* ans;
TreeLinkNode* GetNext(TreeLinkNode* pNode) {
ans = nullptr;
flag = false;
TreeLinkNode* root = nullptr;
TreeLinkNode* tmp = pNode;
while(tmp->next != nullptr) {
tmp = tmp->next;
}
root = tmp;
inorder(root, pNode);
return ans;
}
TreeLinkNode* inorder(TreeLinkNode* root, TreeLinkNode* target) {
if (flag && ans) return ans;
if (!root) return nullptr;
inorder(root->left, target);
if (!flag) {
if (root == target) {
flag = true;
}
} else {
if (!ans) {
ans = root;
return root;
}
}
inorder(root->right, target);
return ans;
}
};
# -*- coding:utf-8 -*-
# class TreeLinkNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
# self.next = None
class Solution:
def GetNext(self, pNode):
# write code here
self.ans = None
self.flag = False
tmp = pNode
while tmp.next is not None:
tmp = tmp.next
root = tmp
self.inorder(root, pNode)
return self.ans
def inorder(self, root, target):
if self.flag and self.ans:
return self.ans
if not root:
return None
self.inorder(root.left, target)
if not self.flag:
if root is target:
self.flag = True
else:
if not self.ans:
self.ans = root
return root
self.inorder(root.right, target)
return self.ans
得走出这种状态，不能一直困在那里面，哪不行就去提升哪，你一动不动那指定改变不了未来，动起来，积少成多才能越来越好
