二叉树遍历144、94、145

本文主要是介绍二叉树遍历144、94、145，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

• 前序遍历_迭代法

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

• 中序遍历_迭代法
• 思路：

1. 将cur一直到树的最左下位置的null，再开始向result加元素。
2. 再依次从stack取元素给cur，用cur.val给res加元素。
3. 再cur = cur.right;//这一句代码很妙

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

• 后序遍历_迭代法

oublic List<Integer> postorderTraversal(TreeNode root){List<Integer> result = new ArrayList<>();if(root == null) return result;Deque<TreeNode> stack = new ArrayDeque<>();stack.push(root);Deque<Integer> outputStack = new ArrayDeque<>();while(!stack.isEmpty()){TreeNode node = stack.pop();outputStack.push(node.val);// 这个左右顺寻保持和result（左-右）一样if(node.left != null) stack.push(node.left);if(node.right != null) stack.push(node.right);}while(!outputStack.isEmpty()){result.add(outputStack.pop());}return result;
}

总结：前序、后序的前四行代码完全一样，后序多定义了一个outputStack

这篇关于二叉树遍历144、94、145的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---