【数据结构与算法】二叉树 前序 中序 后序 非递归实现 极简

本文主要是介绍【数据结构与算法】二叉树 前序 中序 后序 非递归实现 极简，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

节点：

class TreeNode{int val;TreeNode left;TreeNode right;TreeNode(int val){this.val = val;}
}

前序：

 public List<Integer> preorderTraversal(TreeNode root) {List<Integer> result = new ArrayList<>();TreeNode p = root;Stack<TreeNode> stack = new Stack<>();while(p != null || !stack.isEmpty()){if(p != null){result.add(p.val);stack.push(p);p = p.left;}else{p = stack.pop().right;}}return result;}

思路是只要遍历指针p不空，就输出p，然后一直找它的左边，直到null，这时就出栈一个，然后让p指向出栈的右边，重复之前的过程，还是一直找左边。因为树的遍历我们一般都是dfs，深度遍历，深度遍历就是优先往深里找。这里的p其实就是遍历的子树的根，先根那就是先输出p，然后把p压入栈，这样就可以记录右子树了，然后把p设置为左子树相同的处理。只有左子树完了才出栈遍历右子树，仍然是一样的过程。

中序：

    public List<Integer> inorderTraversal(TreeNode root) {List<Integer> result = new ArrayList<>();TreeNode p = root;Stack<TreeNode> stack = new Stack<>();while(p != null || !stack.isEmpty()){if(p != null){stack.push(p);p = p.left;}else{TreeNode node = stack.pop();result.add(node.val);p = node.right;}}return result;}

基本和前序没有区别，只是输出根的位置变了。只有左边没有了才出栈输出根。

后序:

这是我这次关注的，有一次面试偏偏被问到了。今天发现了一个很牛逼的写法，相当简洁，也是按照之前的思路写的。

后序遍历，根的位置可以确定，是在结果队列的最后一个位置，然后根前面是左子树和右子树，难点在于左子树的根和右子树的根怎么放？一般我们可能会想到先放左子树，但是左子树的根确实找不到地方放。其实右子树更好放，因为右子树的根的位置可以确定，就是父节点前面，也就是倒数第二个，这是一个特别有用的规律，直接决定了我们程序的写法将相当简洁。

那么程序逻辑就变了，我们先把根节点放在结果的最后一位，然后再递归处理右子树，在根节点前面放右子树，最后处理左子树，在右子树前面放左子树。为什么先处理右子树呢？就是之前那个发现，因为右子树的根是可以确定位置的，就是倒数第二个位置。

感觉这个思路简直碉堡了。有木有！！！

    public List<Integer> postorderTraversal(TreeNode root) {List<Integer> result = new ArrayList<>();TreeNode p = root;Stack<TreeNode> stack = new Stack<>();while(p != null || !stack.isEmpty()){if(p != null){stack.push(p);result.add(0, p.val);p = p.right;}else{TreeNode node = stack.pop();p = node.left;}}return result;}

这篇关于【数据结构与算法】二叉树 前序 中序 后序 非递归实现 极简的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---