邯郸房产网站,wordpress更新需要多久,网站登陆口提交网站,北京网站建设推广我们从二叉树的根节点 root 开始进行深度优先搜索。
在遍历中的每个节点处#xff0c;我们输出 D 条短划线#xff08;其中 D 是该节点的深度#xff09;#xff0c;然后输出该节点的值。#xff08;如果节点的深度为 D#xff0c;则其直接子节点的深度为 D 1。根节点的…我们从二叉树的根节点 root 开始进行深度优先搜索。
在遍历中的每个节点处我们输出 D 条短划线其中 D 是该节点的深度然后输出该节点的值。如果节点的深度为 D则其直接子节点的深度为 D 1。根节点的深度为 0。
如果节点只有一个子节点那么保证该子节点为左子节点。
给出遍历输出 S还原树并返回其根节点 root。
输入“1-2–3--4-5–6--7” 输出[1,2,5,3,4,6,7]
代码
/*** Definition for a binary tree node.* public class TreeNode {* int val;* TreeNode left;* TreeNode right;* TreeNode(int x) { val x; }* }*/
class Solution {public TreeNode recoverFromPreorder(String S) {LinkedListTreeNode stacknew LinkedList();int pos0;while (posS.length())//逐个遍历{int level0;while (S.charAt(pos)-)//获取当前数字所在层数{pos;level;}int val0;while (posS.length()Character.isDigit(S.charAt(pos)))//提取字符串的数字{valval*10(S.charAt(pos)-0);pos;}TreeNode tempnew TreeNode(val);if(stack.size()level)//栈中元素等于层数根据先序遍历的特点说明当前是在左子树{if(!stack.isEmpty())stack.getLast().lefttemp;}else {//栈中元素不等于层数根据先序遍历的特点说明当前是在又子树需要先将左子树出栈才能获得父节点while (stack.size()level)stack.removeLast();stack.getLast().righttemp;}stack.add(temp);}while (stack.size()1)stack.removeLast();return stack.getLast();}
}
