-
二叉树前序遍历按照 根节点 左子树 右子树 的 顺序进行的,也就是根左右。
-
简易记法:将一个节点分为三个边,分别用不同颜色如图表示,从根节点进入从左边开始沿着边进行遍历,由下图可知,路过的红色部分依次为0,1,3,4,7,2,5,8(后面的中序遍历与后续遍历同理!)
class Solution {
public List<Integer> preorderTraversal(TreeNode root) {
List<Integer> ans = new ArrayList<>();
return preorder_Traversal(root,ans);
}
List<Integer> preorder_Traversal(TreeNode root,List<Integer> ans){
if(root==null)
{
return ans ;
}
ans.add(root.val);//根节点
preorder_Traversal(root.left,ans);//左子树
preorder_Traversal(root.right,ans);//右子树
return ans;
}
}
class Solution {
public List<Integer> preorderTraversal(TreeNode root) {
Deque<TreeNode> stack = new LinkedList<>();// 用一个栈来维护前序顺序
List<Integer> list = new ArrayList<>();//存放最终答案
while(!stack.isEmpty()||root!=null)
{
while(root!=null)
{
stack.push(root); //用栈维护前序顺序,也就是可以退到最终节点的父节点。
list.add(root.val);
root = root.left;//访问过根节点之后访问左子树
}
root = stack.pop().right;//此时此节点已经是叶子节点,左为空,然后让root指向不为空之后的节点的右子树。
}
return list;
}
}
二叉树中序遍历
-
二叉树前序遍历按照 左子树 根节点 右子树 的 顺序进行的,也就是 左 根 右。
class Solution {
public List<Integer> inorderTraversal(TreeNode root) {
List<Integer> ans = new ArrayList<>();
return inorder_Traversal(root,ans);
}
List<Integer> inorder_Traversal(TreeNode root,List<Integer> ans){
if(root==null)
{
return ans ;
}
inorder_Traversal(root.left,ans);//左子树
ans.add(root.val);//根节点
inorder_Traversal(root.right,ans);//右子树
return ans;
}
}
class Solution {
public List<Integer> inorderTraversal(TreeNode root) {
List<Integer> list = new ArrayList<>();//存放最终答案
Deque<TreeNode> stack = new LinkedList<>();// 用一个栈来维护前序顺序
while(!stack.isEmpty()||root!=null)
{
while(root!=null)
{
stack.push(root); //用栈维护中序遍历顺序,也就是可以退到最终节点的父节点。
root = root.left;
}
root = stack.pop();
list.add(root.val); //保存根节点
root = root.right;//此时让节点指向右子树。
}
return list;
}
}
二叉树后序遍历
-
二叉树后序遍历按照 左子树 右子树 根节点 的 顺序进行的,也就是 左 右 根。(图中绿色)
class Solution {
public List<Integer> postorderTraversal(TreeNode root) {
List<Integer> ans = new ArrayList<>();
return postorder_Traversal(root,ans);
}
List<Integer> postorder_Traversal(TreeNode root,List<Integer> ans){
if(root==null)
{
return ans ;
}
postorder_Traversal(root.left,ans);//左子树
postorder_Traversal(root.right,ans);//右子树
ans.add(root.val);//根节点
return ans;
}
}
class Solution {
public List<Integer> postorderTraversal(TreeNode root) {
Deque<TreeNode> stack = new LinkedList<>();
List<Integer> list = new ArrayList<>();
TreeNode pre = null ;
while(!stack.isEmpty()||root!=null)
{
while(root!=null)
{
stack.push(root);
root = root.left;
}
root = stack.pop();
if(root.right==null||pre==root.right)//当前叶子节点没有右节点,那么就把他存入 或者 root的右节点和上一次pre相等时(最右端的情况)
{
list.add(root.val);
pre = root;//记录状态
root=null; //防止root等于pre
}
else
{
stack.push(root);
root = root.right;
}
}
return list;
}
}