04-重建二叉树
输入某二叉树的前序遍历和中序遍历的结果，请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6}，则重建二叉树并返回。
前序遍历一棵树，首先访问的是它的根节点，然后是左子树上的节点，然后是右子树上的节点。而中序遍历一棵树，首先访问它左子树上的节点，其次是根节点，然后是右子树上的节点。因此，给定了前序遍历pre和中序遍历tin的结果，就可以确定，根节点是pre[0]。在tin中找出根节点的位置，它左边的节点就是左子树上的，右边的节点是右子树上的。通过计算这些节点的数目，就可以在pre上也划分出左右子树节点的范围。使用递归，构造左右子树。
LeetCode上的对应问题也是类似的。后序遍历中，根节点是最后一个访问的，因此也可以直接找出根节点。然后再根据中序遍历结果找出左右子树节点的范围，结合后序遍历结果，同样使用递归来构造左右子树即可。
def reConstructBinaryTree(self, pre, tin):
if not pre:
return None
root = TreeNode(pre[0])
root_idx = tin.index(pre[0])
root.left = self.reConstructBinaryTree(pre[1:1+root_idx],
tin[:root_idx])
root.right = self.reConstructBinaryTree(pre[1+root_idx:],
tin[root_idx+1:])
return root
class Solution {
public:
TreeNode *reConstructBinaryTree(vector<int> pre, vector<int> vin) {
if (pre.size() == 0) return nullptr;
TreeNode *root = new TreeNode(pre[0]);
int root_idx = find(vin.begin(), vin.end(), pre[0]) - vin.begin();
root->left = reConstructBinaryTree(vector<int>(pre.begin()+1, pre.begin()+1+root_idx), vector<int>(vin.begin(), vin.begin()+root_idx));
root->right = reConstructBinaryTree(vector<int>(pre.begin()+1+root_idx, pre.end()), vector<int>(vin.begin()+1+root_idx, vin.end()));
return root;
}
};
17-树的子结构
输入两棵二叉树A，B，判断B是不是A的子结构。（ps：我们约定空树不是任意一个树的子结构）
子树和子结构不一样。
B是A的子树，表示A的某个子树A’和B完全一样（包括节点数、节点关系）。
而B是A的子结构，是指B可以通过删掉A的某个子树A’的一些节点得到，相应的，与之相关的节点关系也被删减。
判断子结构跟判断子树的思路本质上是一样的，只需要在某些地方做一些修改。
判断子树的相似问题来自于LeetCode，我们可以定义递归函数HasSubStructure(A, B)来进行判断，如果树B是树A的子结构，则返回True;否则返回False。在递归过程中：
- 如果B是空树，按定义B不是A的子结构，因为空树不是任意树的子结构。但是在递归过程中，B很有可能不是原来的B，而只是它的一棵子树。这种情况下，函数是应该返回
True的，因为它说明A的某一个部分，“包含”了B的一个子树。接下来的任务，就是判断B的其他子树有没有被A包含。可以给HasSubStructure加一个带有缺省值的参数，来标识当前传参B是否是一个子树。 -
如果A是空树，但B不是空树，函数
HasSubStructure则毫无疑问返回False。这是因为非空树B不可能是空树的子结构。 - 如果A、B都不为空树，且A的根节点和B的根节点值一样时，会有两种可能：1）B是A左子树或右子树的子结构；2）B的左子树是A左子树的子结构，而B的右子树是A右子树的子结构。即是说，将A变成B所要删减的节点，不包括A的根节点。1）和2）都是有可能的，只有在递归尝试了
HasSubStructure(A.left, B)，HasSubStructure(A.right, B)和HasSubStructure(A.left, B.left) and HasSubStructure(A.right, B.right)，并且都返回False之后，才能说明B不是A的子结构。 - 如果A、B都不为空树，且A的根节点和B的根节点值不一样时，如果B是A的子结构，那就只能是A的左子树或者右子树的子结构。返回
HasSubStructure(A.left, B) or HasSubStructure(A.right, B).
代码如下：
class Solution:
def HasSubStructure(self, A, B, child=False):
if not B:
return child
elif not A:
return False
elif A.val == B.val:
return (self.HasSubStructure(A.left, B.left, True) and self.HasSubStructure(A.right, B.right, True)) \
or self.HasSubStructure(A.left, B, child) or self.HasSubStructure(A.right, B, child)
else:
return self.HasSubStructure(A.left, B, child) or self.HasSubStructure(A.right, B, child)
class Solution {
public:
bool HasSubtree(TreeNode *pRoot1, TreeNode *pRoot2, bool child = false) {
if (!pRoot2) return child;
if (!pRoot1) return false;
if (pRoot1->val == pRoot2->val)
return (HasSubtree(pRoot1->left, pRoot2->left, true) &&
HasSubtree(pRoot1->right, pRoot2->right, true)) ||
HasSubtree(pRoot1->left, pRoot2, child) ||
HasSubtree(pRoot1->right, pRoot2, child);
else
return HasSubtree(pRoot1->left, pRoot2, child) ||
HasSubtree(pRoot1->right, pRoot2, child);
}
};
除了单行太长以外，看上去挺简洁的……
判断B是否为A的子树是类似的。但是要注意空树是任意树的子树（跟子结构的定义相反）。假设判断函数为isSubtree(A, B)，判断子树的逻辑分析过程如下：
- 如果B是空树，那么按照定义，B应该是A的子树。函数
isSubtree直接返回True。 - 如果A是空树，但B不是空树，函数
isSubtree直接返回False。这是因为非空树B不可能是空树的子树。 - 如果A、B都不为空树，且A的根节点和B的根节点值不一样时，如果B是A的子树，那就只能是A的左子树或者右子树的子树。返回
isSubtree(A.left, B) or isSubtree(A.right, B). - 如果A、B都不为空树，且A的根节点和B的根节点值一样时，会有两种可能：1）B是A左右子树的子树；2）A和B相同。1）和2）都是有可能的，首先要比较A和B是否相同。使用另一个函数
compare(A, B)来作比较。如果不同，再递归地尝试isSubtree(A.left, B)，isSubtree(A.right, B)。
判断子树的代码如下：
class Solution:
def compare(self, A, B):
if not A and not B:
return True
if not A or not B or A.val != B.val:
return False
return self.compare(A.left, B.left) and self.compare(A.right, B.right)
def isSubtree(self, A, B):
if not B:
return True
if not A:
return False
if A.val != B.val:
return self.isSubtree(A.left, B) or self.isSubtree(A.right, B)
else:
return self.compare(A, B) or self.isSubtree(A.left, B) or self.isSubtree(A.right, B)
class Solution {
bool compare(TreeNode *s, TreeNode *t) {
if (!s && !t) return true;
if (!s || !t || s->val != t->val) return false;
return compare(s->left, t->left) && compare(s->right, t->right);
}
public:
bool isSubtree(TreeNode* s, TreeNode* t) {
if (!t) return true;
if (!s) return false;
if (s->val == t->val && compare(s, t))
return true;
return isSubtree(s->left, t) || isSubtree(s->right, t);
}
};
这道题快速地一次做对的关键，就是要先分析在递归过程中，如何进行逻辑判断。这是在写复杂代码前至关重要的一个步骤。没有经过思考就下笔，代码可能会藏有诸多漏洞，而且冗长丑陋。所以，在下次做题之前，一定要先对问题进行分析，尤其是要搞明白边界的细节问题之后，方可开始书写代码。
18-二叉树的镜像
操作给定的二叉树，将其变换为源二叉树的镜像。
解释这道题的时间，多于写出代码并通过测试的时间。
def Mirror(self, root):
if not root:
return None
root.left, root.right = self.Mirror(root.right), self.Mirror(root.left)
return root
class Solution {
public:
void Mirror(TreeNode *pRoot) {
if (!pRoot) return;
TreeNode *tmp = pRoot->left;
pRoot->left = pRoot->right, pRoot->right = tmp;
Mirror(pRoot->left), Mirror(pRoot->right);
}
};
22-从上往下打印二叉树
从上往下打印出二叉树的每个节点，同层节点从左至右打印。
（返回节点值列表）
层次遍历二叉树 (traverse in level order)。使用一个列表level来记录每一层所有的节点。从左到右访问这些节点，并依次将它们的孩子添加进新一层的节点列表中。
def PrintFromTopToBottom(self, root):
level = [root]
rtn = []
while level:
next_level = []
for each in level:
if each:
rtn.append(each.val)
next_level.append(each.left)
next_level.append(each.right)
level = next_level
return rtn
class Solution {
public:
vector<int> PrintFromTopToBottom(TreeNode* root) {
if (!root) return {};
vector<TreeNode*> level, next_level;
level.push_back(root);
vector<int> rtn;
while (!level.empty()) {
next_level.clear();
for (TreeNode *each: level) {
if (each) {
rtn.push_back(each->val);
next_level.push_back(each->left);
next_level.push_back(each->right);
}
}
level = next_level;
}
return rtn;
}
};
23-二叉搜索树的后序遍历序列
输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历的结果。如果是则输出Yes,否则输出No。假设输入的数组的任意两个数字都互不相同。
（返回True或False）
后序遍历中，树的左子树首先被访问，然后是右子树，最后才是根节点。在二叉搜索树中，左子树的节点值都小于根节点的值，而右子树的节点值都大于根节点的值。因此，在后序遍历序列中，最后一个元素是根节点的节点值。而序列的前部分S_1属于左子树，值小于最后一个元素（根节点值）；然后跟着的一段S_2，属于右子树，值大于最后一个元素。如果S_1和S_2序列也符合这个规律，那么这个后序遍历序列就是来自于一个二叉搜索树的。因此，程序的做法如下：
- 检查当前序列是否存在点
i，使得S[:i]的值都小于S[-1]（根节点值），而S[i:-1]的值都大于S[-1]。 - 递归地检查
S[:i]和S[i:-1]是否也满足。
def VerifySquenceOfBST(self, sequence):
if not sequence:
return False
root = sequence[-1]
# separate left/right subtree
spoint = -1
for i, v in enumerate(sequence[:-1]):
if v > root and spoint == -1:
spoint = i
if spoint != -1 and v < root:
return False
left, right = True, True
if spoint > 1:
left = self.VerifySquenceOfBST(sequence[:spoint])
if spoint > -1 and len(sequence) - spoint - 1 > 1:
right = self.VerifySquenceOfBST(sequence[spoint:-1])
return left and right
class Solution {
public:
bool VerifySquenceOfBST(vector<int> sequence) {
if (!sequence.size()) return false;
int spoint = -1, root = sequence.back();
for (int i = 0; i < sequence.size() - 1; ++i) {
if (sequence[i] > root && spoint == -1)
spoint = i;
if (spoint != -1 && sequence[i] < root)
return false;
}
bool left = true, right = true;
if (spoint > 1)
left = VerifySquenceOfBST(vector<int>(sequence.begin(), sequence.begin()+spoint));
if (spoint < sequence.size() - 1)
right = VerifySquenceOfBST(vector<int>(sequence.begin()+spoint, sequence.end()-1));
return left && right;
}
};
24-二叉树中和为某一值的路径
输入一颗二叉树的根节点和一个整数，打印出二叉树中结点值的和为输入整数的所有路径。路径定义为从树的根结点开始往下一直到叶结点所经过的结点形成一条路径。(注意: 在返回值的list中，数组长度大的数组靠前)
DFS遍历树，可以得到树的所有路径。在行进过程中，逐渐累加路径的节点值和。如果到达叶节点时，累加值等于expectNumber，就把该路径添加到答案中。走完所有路径后，将答案中的路径按长度由长到短排序即可。
def FindPath(self, root, expectNumber):
ans = []
def dfs(node, path, acc=0):
if not node:
return
path = path + [node.val]
acc += node.val
if not node.left and not node.right:
if acc == expectNumber:
ans.append(path)
return
dfs(node.left, path, acc)
dfs(node.right, path, acc)
dfs(root, [])
return sorted(ans, key=lambda x: -len(x))
class Solution {
int EN;
vector<vector<int>> ans;
void dfs(TreeNode *node, vector<int> &path, int acc=0) {
if (!node->left && !node->right) {
if (acc == EN)
ans.push_back(vector<int>(path.begin(), path.end()));
return;
}
if (node->left) {
path.push_back(node->left->val);
dfs(node->left, path, acc + node->left->val);
path.pop_back();
}
if (node->right) {
path.push_back(node->right->val);
dfs(node->right, path, acc + node->right->val);
path.pop_back();
}
}
public:
vector<vector<int> > FindPath(TreeNode *root, int expectNumber) {
if (!root) return {};
EN = expectNumber;
ans.clear();
vector<int> path = {root->val};
dfs(root, path, root->val);
return ans;
}
};
26-二叉搜索树与双向链表
输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的双向链表。要求不能创建任何新的结点，只能调整树中结点指针的指向。
（返回双向链表中最左的节点）
我的做法是中序遍历二叉搜索树，每访问一个节点就将它添加进一个列表中。这样遍历完，由于是二叉搜索树，会得到一个有序节点列表。然后，将这个列表中的节点按顺序调整指针指向即可。过程非常简单清晰。
def Convert(self, pRootOfTree):
if not pRootOfTree:
return None
nodes = []
def inorder(node):
if not node:
return
inorder(node.left)
nodes.append(node)
inorder(node.right)
inorder(pRootOfTree)
nodes[0].left, nodes[-1].right = None, None
for i in range(len(nodes)-1):
nodes[i].right = nodes[i+1]
nodes[i+1].left = nodes[i]
return nodes[0]
当然，这道题也可以用递归，过程同样简洁。已知Convert函数返回一个有序双向链表。那么只要处理左右子树：Convert(root.left)，Convert(root.right)。处理完毕后，返回两个有序的双向列表left和right。其中，left的节点值小于根节点值，而right中的节点值大于根节点值。left和right皆有序。要将left，根节点，和right串成一个双向链表，只需要将左子树形成的链表最右的节点，和根节点，以及右子树形成的链表最左的节点，三点连接在一起即可。最后得到的链表，是一个包含了树所有节点，且有序的双向链表。
def Convert(self, pRootOfTree):
if not pRootOfTree:
return None
left = self.Convert(pRootOfTree.left)
if left:
while left.right:
left = left.right
pRootOfTree.left, left.right = left, pRootOfTree
right = self.Convert(pRootOfTree.right)
if right:
while right.left:
right = right.left
pRootOfTree.right, right.left = right, pRootOfTree
while pRootOfTree.left:
pRootOfTree = pRootOfTree.left
return pRootOfTree
38-二叉树的深度
输入一棵二叉树，求该树的深度。从根结点到叶结点依次经过的结点（含根、叶结点）形成树的一条路径，最长路径的长度为树的深度。
非常简单的题~DFS就好了。对一棵树递归求左子树和右子树的深度，然后取它们之后深的为该棵树的深度。
def TreeDepth(self, pRoot, depth=0):
if not pRoot:
return depth
return max(self.TreeDepth(pRoot.left, depth+1), self.TreeDepth(pRoot.right, depth+1))
class Solution {
public:
int TreeDepth(TreeNode *pRoot) {
if (!pRoot) return 0;
int left_depth = TreeDepth(pRoot->left), right_depth = TreeDepth(pRoot->right);
return 1 + (left_depth > right_depth ? left_depth : right_depth);
}
};
39-平衡二叉树
输入一棵二叉树，判断该二叉树是否是平衡二叉树。
平衡二叉树的定义是：它是一棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树（百度百科）。这个定义是个递归定义，所以我们的解法也是递归解法……先递归地求出左右子树的深度（为了避免重复计算，可以将子树的深度存在一个字典中）。如果它们的深度差不超过1，这棵树就是平衡二叉树。然后，递归地判断左右子树。如果左右子树同样也是平衡二叉树的话，这棵树就是平衡二叉树。
def IsBalanced_Solution(self, pRoot):
if not pRoot:
return True
mem = {}
def dfs(node):
if not node:
return 0
left_d, right_d = dfs(node.left), dfs(node.right)
depth = max(left_d, right_d) + 1
mem[node] = depth
return depth
dfs(pRoot)
def avl(node):
if not node:
return True
left_depth = mem.get(node.left, 0)
right_depth = mem.get(node.right, 0)
if abs(left_depth - right_depth) <= 1:
if avl(node.left) and avl(node.right):
return True
return False
return avl(pRoot)
class Solution {
unordered_map<TreeNode*, int> mem;
int TreeDepth(TreeNode *pRoot) {
if (!pRoot) return 0;
if (mem.count(pRoot)) return mem[pRoot];
int left_depth = TreeDepth(pRoot->left),
right_depth = TreeDepth(pRoot->right);
int depth = 1 + (left_depth > right_depth ? left_depth : right_depth);
mem[pRoot] = depth;
return depth;
}
bool avl(TreeNode *node) {
if (!node) return true;
int left_depth = TreeDepth(node->left), right_depth = TreeDepth(node->right);
if (left_depth - right_depth <= 1 && right_depth - left_depth <= 1)
return avl(node->left) && avl(node->right);
return false;
}
public:
bool IsBalanced_Solution(TreeNode *pRoot) {
mem.clear();
TreeDepth(pRoot);
return avl(pRoot);
}
};
57-二叉树的下一个结点
给定一个二叉树和其中的一个结点，请找出中序遍历顺序的下一个结点并且返回。注意，树中的结点不仅包含左右子结点，同时包含指向父结点的指针。
如果给定节点有右子树，那么中序遍历的下一个节点会在它的右子树上。具体地说，是在右子树最左的节点上。如果给定节点没有右子树，那么中序遍历访问完给定节点后，应该会回退到它的父节点。如果给定节点是父节点的左孩子，那么下一个访问的应该就是它的父节点（因为父节点的左子树都访问完了，轮到它了）。如果是父节点的右孩子，说明父节点所在子树上的节点都以访问完毕（因为父节点的右子树也访问完了），继续回退到父节点的父节点。直到遇到一个父节点，是从它的左孩子回退来的。这个父节点的左子树刚刚被访问完，下一个被访问的会是它自己。于是这种情况下，返回值就是这个父节点。
def GetNext(self, pNode):
if pNode.right:
pNode = pNode.right
while pNode.left:
pNode = pNode.left
else:
child, pNode = pNode, pNode.next
while pNode and child != pNode.left:
child, pNode = pNode, pNode.next
return pNode
class Solution {
public:
TreeLinkNode *GetNext(TreeLinkNode *pNode) {
if (!pNode) return nullptr;
if (pNode->right) {
pNode = pNode->right;
while (pNode->left)
pNode = pNode->left;
} else {
TreeLinkNode *child = pNode;
pNode = pNode->next;
while (pNode && child != pNode->left) {
child = pNode, pNode = pNode->next;
}
}
return pNode;
}
};
58-对称的二叉树
请实现一个函数，用来判断一颗二叉树是不是对称的。注意，如果一个二叉树同此二叉树的镜像是同样的，定义其为对称的。
将二叉树水平翻转获得镜像后，比较原来二叉树是否和镜像相同。如果相同，就是对称的二叉树。
def isSymmetrical(self, pRoot):
def mirror(node):
if not node:
return None
new_node = TreeNode(node.val)
new_node.left, new_node.right = mirror(node.right), mirror(node.left)
return new_node
def compare(node1, node2):
if not node1 and not node2:
return True
if not node1 or not node2 or node1.val != node2.val:
return False
return compare(node1.left, node2.left) and compare(node2.right, node2.right)
return compare(pRoot, mirror(pRoot))
第二种做法是，直接在原来二叉树上进行比较。递归地比较左右子树。如果左子树上的某个节点值和右子树对应位置上的节点值不相等，而该二叉树不是对称二叉树。求对称位置的逻辑不如用代码表达。
def isSymmetrical(self, pRoot):
if not pRoot:
return True
def compare(t1, t2):
if not t1 and not t2:
return True
if not t1 or not t2 or t1.val != t2.val:
return False
return compare(t1.left, t2.right) and compare(t1.right, t2.left)
return compare(pRoot.left, pRoot.right)
class Solution {
bool compare(TreeNode *t1, TreeNode *t2) {
if (!t1 && !t2) return true;
if (!t1 || !t2 || t1->val != t2->val) return false;
return compare(t1->left, t2->right) && compare(t1->right, t2->left);
}
public:
bool isSymmetrical(TreeNode *pRoot) {
if (!pRoot) return true;
return compare(pRoot->left, pRoot->right);
}
};
59-按之字形顺序打印二叉树
请实现一个函数按照之字形打印二叉树，即第一行按照从左到右的顺序打印，第二层按照从右至左的顺序打印，第三行按照从左到右的顺序打印，其他行以此类推。
我的代码是在22题的基础上修改一下得到的。设置一个flag，每访问完一层更改flag。如果flag是True，就反着读取节点值。否则正向读取。
def Print(self, root):
level = [root]
rtn = []
flag = False
while level:
next_level = []
tmp = []
for each in level:
if each:
tmp.append(each.val)
next_level.append(each.left)
next_level.append(each.right)
if flag and tmp:
rtn.append(tmp[::-1])
if not flag and tmp:
rtn.append(tmp)
level = next_level
flag = not flag
return rtn
class Solution {
public:
vector<vector<int> > Print(TreeNode *pRoot) {
if (!pRoot) return {};
vector<TreeNode *> level, next_level;
level.push_back(pRoot);
bool flag = false;
vector<vector<int>> rtn;
vector<int> tmp;
while (!level.empty()) {
next_level.clear();
tmp.clear();
for (TreeNode *each : level) {
if (each) {
tmp.push_back(each->val);
next_level.push_back(each->left);
next_level.push_back(each->right);
}
}
if (!tmp.empty()) {
if (flag)
rtn.push_back(vector<int>(tmp.rbegin(), tmp.rend()));
else
rtn.push_back(tmp);
}
flag = !flag;
level = next_level;
}
return rtn;
}
};
61-序列化二叉树
请实现两个函数，分别用来序列化和反序列化二叉树
二叉树的序列化是指：把一棵二叉树按照某种遍历方式的结果以某种格式保存为字符串，从而使得内存中建立起来的二叉树可以持久保存。序列化可以基于先序、中序、后序、层序的二叉树遍历方式来进行修改，序列化的结果是一个字符串，序列化时通过 某种符号表示空节点（#），以 ！ 表示一个结点值的结束（value!）。
二叉树的反序列化是指：根据某种遍历顺序得到的序列化字符串结果str，重构二叉树。
如果使用#来表示空节点，那么无论是前序中序后序层次遍历得到的序列都是能唯一代表一棵树的。我的代码使用了前序遍历。每访问一个节点，就将它的节点值放进串行化序列中。解码时，也按前序遍历的方式将序列中的值变回节点。
def Serialize(self, root):
"""Encodes a tree to a single string.
In a preorder style.
:type root: TreeNode
:rtype: str
"""
node_list = []
def preorder(node):
if not node:
node_list.append('#')
return
node_list.append(str(node.val))
preorder(node.left)
preorder(node.right)
preorder(root)
return ' '.join(node_list)
def Deserialize(self, data):
"""Decodes your encoded data to tree.
:type data: str
:rtype: TreeNode
"""
# reconstruct a tree with its hierarchical order sequence
if len(data) == 0:
return None
data = iter(data.split())
def preorder():
val = next(data)
if val == '#':
return None
node = TreeNode(int(val))
node.left = preorder()
node.right = preorder()
return node
root = preorder()
return root
class Solution {
vector<int> buff;
void preorder_ser(TreeNode *root) {
if (!root) {
buff.push_back(0x7fffffff);
return;
}
buff.push_back(root->val);
preorder_ser(root->left), preorder_ser(root->right);
}
TreeNode* preorder_des(int *&p) {
if (*p == 0x7fffffff) {
++p;
return nullptr;
}
TreeNode *node = new TreeNode(*p);
++p;
node->left = preorder_des(p);
node->right = preorder_des(p);
return node;
}
public:
char *Serialize(TreeNode *root) {
buff.clear();
preorder_ser(root);
int *rtn = new int[buff.size()];
copy(buff.begin(), buff.end(), rtn);
return (char*) rtn;
}
TreeNode *Deserialize(char *str) {
int *p = (int*) str;
return preorder_des(p);
}
};
62-二叉搜索树的第k个结点
给定一棵二叉搜索树，请找出其中的第k小的结点。例如， （5，3，7，2，4，6，8） 中，按结点数值大小顺序第三小结点的值为4。
使用一个字典来储存“全局变量”counter（计算已经访问多少个节点）和ans（返回的答案）（关于外层变量作用域参见StackOverflow回答）。对树进行中序遍历。每访问一个节点就让counter加一。当counter等于k时，就将ans设为正在访问的节点。剩下未访问的节点就不需要再进行访问了。如果counter >= k，说明已经找到了第k个节点，剩下的节点无需访问直接返回。
def KthNode(self, pRoot, k):
nl = {'counter': 0, 'ans': None}
def inorder(node):
if nl['counter'] >= k or not node:
return
inorder(node.left)
if nl['counter'] >= k:
return
nl['counter'] += 1
if nl['counter'] == k:
nl['ans'] = node
return
inorder(node.right)
inorder(pRoot)
return nl['ans']
class Solution {
int count;
TreeNode *ans;
void inorder(TreeNode *pRoot, int k) {
if (count >= k || !pRoot) return;
inorder(pRoot->left, k);
if (count >= k) return;
++count;
if (count == k) {
ans = pRoot;
return;
}
inorder(pRoot->right, k);
}
public:
TreeNode *KthNode(TreeNode *pRoot, int k) {
count = 0, ans = nullptr;
inorder(pRoot, k);
return ans;
}
};