大型网站建设网站推广,标志logo设计,义乌建设局网站,室内设计联盟邀请码怎么弄二叉树的非递归遍历 文章目录 二叉树的非递归遍历前序遍历-栈层序遍历-队列中序遍历-栈后序遍历-栈 前序遍历-栈
首先我们应该创建一个Stack 用来存放节点#xff0c;首先我们想要打印根节点的数据#xff0c;此时Stack里面的内容为空#xff0c;所以我们优先将头结点加入S…二叉树的非递归遍历 文章目录 二叉树的非递归遍历前序遍历-栈层序遍历-队列中序遍历-栈后序遍历-栈 前序遍历-栈
首先我们应该创建一个Stack 用来存放节点首先我们想要打印根节点的数据此时Stack里面的内容为空所以我们优先将头结点加入Stack。之后我们应该先打印左子树然后右子树所以先加入Stack的就是右子树然后左子树。
public ListInteger preorderTraversal(TreeNode root) {ListInteger res new ArrayList();if (root null) {return res;}StackTreeNode stack new Stack();//1.根节点入栈stack.push(root);//2.栈不为空while (!stack.isEmpty()) {//2.1出栈需暂时保存出栈元素TreeNode tmp stack.pop();res.add(tmp.val);//2.2左右子树不为空的情况下出栈元素的右子树入栈左子树入栈if (tmp.right ! null) {stack.push(tmp.right);}if (tmp.left ! null) {stack.push(tmp.left);}}return res;
}
层序遍历-队列
首先我们应该创建一个Queue用来存放节点首先我们想要打印根节点的数据此时Queue里面的内容为空所以我们优先将头结点加入Queue。之后我们应该先打印左子树然后右子树所以先加入Queue的就是左子树然后右子树。
public ListListInteger levelOrder(TreeNode root) {ListListInteger res new ArrayList();if (root null) {return res;}QueueTreeNode queue new LinkedList();//1.根节点入队列queue.offer(root);//2.队列不为空while (!queue.isEmpty()) {//2.1获取当前队列的元素ListInteger level new ArrayList();int size queue.size();for (int i 0; i size; i) {//2.1.1出队列需暂时保存出队元素TreeNode tmp queue.poll();level.add(tmp.val);//2.1.2左右子树不为空的情况下出队元素的左子树入队右子树入队if (tmp.left ! null) {queue.offer(tmp.left);}if (tmp.right ! null) {queue.offer(tmp.right);}}//2.2当前队列元素加入到res中res.add(level);}return res;
}中序遍历-栈
同理创建一个 Stack。
尽可能的将这个节点的左子树压入 Stack此时栈顶的元素是最左侧的元素其目的是找到一个最小单位的子树(也就是最左侧的一个节点)并且在寻找的过程中记录了来源才能返回上层同时在返回上层的时候已经处理完毕左子树了。
当处理完最小单位的子树时返回到上层处理了中间节点。如果把整个左中右的遍历都理解成子树的话就是处理完 左子树-中间(就是一个节点)-右子树
如果有右节点其也要进行中序遍历。
public ListInteger inorderTraversal(TreeNode root) {ListInteger res new ArrayList();if (root null) {return res;}StackTreeNode stack new Stack();TreeNode cur root;while (true) {//1.cur从根节点出发一直向左保存左子树直到curnullwhile (cur ! null) {stack.push(cur);cur cur.left;}//2.若栈为空退出循环if (stack.isEmpty()) {break;}//3.出栈TreeNode tmp stack.pop();res.add(tmp.val);//4.cur指向出栈元素的右子树//若为空则继续出栈若不为空再继续向左保存子树cur tmp.right;}return res;
}后序遍历-栈
同理创建一个 Stack。
尽可能的将这个节点的左子树压入 Stack此时栈顶的元素是最左侧的元素。
该元素无右子树或者右子树已经访问过则可以处理该元素并用prev记录当前已处理的元素
否则访问右子树进行后序遍历 public ListInteger postorderTraversal(TreeNode root) {ListInteger res new ArrayList();if (root null) {return res;}StackTreeNode stack new Stack();TreeNode cur root;TreeNode prev null;while (true) {//1.cur从根节点出发一直向左保存左子树直到curnullwhile (cur ! null) {stack.push(cur);cur cur.left;}//2.若栈为空退出循环if (stack.isEmpty()) {break;}//3.得到栈顶元素先不访问满足条件才可以访问TreeNode tmp stack.peek();//4.若栈顶元素无右子树或者右子树已被访问则可以访问//若prevtmp.right则tmp一定是其右子树的根节点。因为此时右子树已访问完毕if (tmp.right null || tmp.right prev) {stack.pop();res.add(tmp.val);prev tmp;} else { //5.cur指向栈顶元素的右子树cur tmp.right;}}return res;}
