【LeetCode】144. Binary Tree Preorder Traversal 二叉树先序遍历的非递归实现

本文主要是介绍【LeetCode】144. Binary Tree Preorder Traversal 二叉树先序遍历的非递归实现，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目：

翻译：给定一个二叉树，返回先序遍历的序列。

分析：二叉树的先序遍历、中序遍历及后序遍历算法是数据结构中最基础的遍历算法。

            先序遍历：先访问根节点的数据，再访问左孩子节点的数据，最后访问右孩子节点的数据。图中例子先序遍历输出的序列为：【1，2，3】。

            中序遍历：先访问左孩子节点的数据，再访问根节点的数据，最后访问右孩子节点的数据。图中例子中序遍历输出的序列为：【1，3，2】。

            后序遍历：先访问左孩子节点的数据，再访问右孩子节点的数据，最后访问根节点的数据。图中例子后序遍历输出的序列为：【3，2，1】。

      

            这三种遍历算法若用递归来写是非常简单的，但是如果采用非递归的方式来实现，相对比较复杂。

            以先序遍历为例，可以使用栈的数据结构来实现先序遍历的非递归方法。具体操作如下：

                   1.若二叉树为空，则返回空序列，结束；若不为空，转2；

                   2.新建一个空栈，将根节点加入栈中；

                   3.若栈不为空，取出栈顶节点，访问该节点的数据（将栈顶元素加入返回的序列中）；

                      判断该节点的【右节点】是否为空，若不为空，将该节点的右节点加入到栈中；

                      判断该节点的【左节点】是否为空，若不为空，将该节点的左节点加入到栈中；

                    （注意：此处是先判断右节点，再判断左节点，因为栈的特点是“后进先出”，左节点总在右节点先遍历，所以要后加入栈中。）

                   4.重复3，直到栈为空，返回最终得到的先序遍历序列。

代码：

         在下面的代码中使用了C#中的List来实现一个栈。

/*** Definition for a binary tree node.* public class TreeNode {*     public int val;*     public TreeNode left;*     public TreeNode right;*     public TreeNode(int x) { val = x; }* }*/
public class Solution {public IList<int> PreorderTraversal(TreeNode root) {List<int> results=new List<int>();if(root==null)return results;List<TreeNode> stack=new List<TreeNode>();//新建一个队列stack.Add(root);while(stack.Count()!=0)//若栈不为空，取出栈顶元素，访问数值，判断左右孩子是否为空，若不为空，加入栈，先加右孩子，再加左孩子{TreeNode temp=stack.Last();//取出栈顶元素stack.Remove(stack.Last());//移除results.Add(temp.val);if(temp.right!=null)stack.Add(temp.right);if(temp.left!=null)stack.Add(temp.left);}return results;}
}

             

这篇关于【LeetCode】144. Binary Tree Preorder Traversal 二叉树先序遍历的非递归实现的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---