We run a preorder depth first search on the root of a binary tree.
At each node in this traversal, we output D dashes (where D is the depth of this node), then we output the value of this node. (If the depth of a node is D, the depth of its immediate child is D+1. The depth of the root node is 0.)
If a node has only one child, that child is guaranteed to be the left child.
Given the output S of this traversal, recover the tree and return its root.
Input: "1-2--3--4-5--6--7"
Output: [1,2,5,3,4,6,7]
这题我喜欢用recursion写 代码简洁
如何判断一个节点有没有左孩子,只要看它的下一个节点的深度是不是当前的深度加1。
当前的深度,可以由--的长度算出。
如果--的个数不match,则这个节点不是上一个节点的孩子。
用preorder traversal做一下就好了。
其实比较routine
class Solution {
public TreeNode recoverFromPreorder(String S) {
int[] index = new int[]{-1};
return helper(S, index, 0);
}
private TreeNode helper(String s, int[] index, int depth) {
int fast = index[0];
if (fast + 1 >= s.length()) return null;
while (fast + 1 < s.length() && s.charAt(fast + 1) == '-' ) fast++;
int curDepth = fast - index[0];
if (curDepth != depth) return null; //这是本题的关键, 如果深度不match, 则返回null。
int n = 0;
while (fast + 1 < s.length() && Character.isDigit(s.charAt(fast + 1))) {
n *= 10;
n += s.charAt(++fast) - '0';
}
TreeNode node = new TreeNode(n);
index[0] = fast;
node.left = helper(s, index, curDepth + 1);
node.right = helper(s, index, curDepth + 1);
return node;
}
}
网友评论