深度优先遍历--从先序遍历还原二叉树

题目

题号

思路

    根据题意，字符"-"的个数+1即以当前为叶子节点构成的树的深度

    已知，如果节点只有一个子节点，则一定是左子节点，故只会有两种情况：

        当前节点是父节点的左子节点（如果存在则优先为左子节点）

        当前节点是其祖节点的右子节点（条件一不成立的情况下一定成立）

    根据以上分析的两个条件可知，需要有一次"回退"判断条件二的过程，这可以借助栈来实现

实现