文档章节

[二叉树专题]求二叉树的前中后遍历(递归,迭代)

十一11
 十一11
发布于 2016/04/20 15:03
字数 521
阅读 30
收藏 0
/* 前序递归遍历
1. 如果二叉树为null,则直接返回
2. 如果二叉树不为null,先访问根节点再访问左子树,最后访问右子树
*/
public static void preorderTraversalRec(TreeNode root){
    if(root == null){
        return ;
    }
    System.out.print(root.val + " ");
    preorderTraversalRec(root.left);
    preorderTraversalRec(root.right);
}
/*前序迭代遍历
用一个辅助stack,总是把右孩子放进栈。
*/
public static void preorderTraversal(TreeNode root){
    if(root == null)
        return null;
    
    Stack<TreeNode> stack = new Stack<TreeNode>();
    stack.push(root);
    
    while(!stack.isEmpty()){
        TreeNode cur= stack.pop();
        System.out.print(cur.val + " ");
        
        //关键点:先压入右孩子,再压入左孩子,这样在出栈的时会先打印左孩子,再打印右孩子。
        if(cur.right != null){
            stack.push(cur.right);
        }
        if(cur.left != null){
            stack.push(cur.left);
        }
    }  
}

/*中序递归遍历
1。如果二叉树为null,则直接返回
2. 如果二叉树不为null,则先访问左子树,再访问根节点,最后访问右子树。
*/
public static void inorderTravelsalRec(TreeNode root){
    if(root == null){
        return ;
    }
    
    inorderTravelsalRec(root.left);
    System.out.print(root.val + " ");
    inorderTravelsalRec(root.right);
}
/*中序迭代遍历
用栈先把根节点的所有左孩子都添加到栈内,然后输出栈顶元素,再处理栈顶元素的右子树
*/
publiv static void inorderTravelsal(TreeNode root){
    if(root == null){
        return ;
    }
    stack<TreeNode> stack = new Stack<TreeNode>();
    TreeNode cur = root;
    while(true){
        while(cur != null){ //先添加所有的左孩子到栈内
            stack.push(cur);
            cur = cur.left;
         }
         if(stack.isEmpty()){
             break;
         }
         
         //因为此时已经没有左孩子,所以输出栈顶元素
         cur = stack.pop();
         System.out.print(cur.val + " ");
         cur = cur.right;
    }
}
/*后序递归遍历
1.如果二叉树为null,则直接返回;
2.如果二叉树不为null,先访问左子树,再访问右子树,最后访问根节点
*/
public static void postorderTravelsalRec(TreeNode root){
    if(root == null){
        return ;
    }
    
    postorderTravelsalRec(root.left);
    postorderTravelsalRec(root.right);
    System.out.print(root.val + " ");
}
/*后序迭代遍历
*/
public static void postorderTravelRec(TreeNode root){
    if(root == null){
        return ;
    }
    
    Stack<TreeNode> s = new Stack<TreeNode>();//第一个stack用于添加node和他的左右孩子
    Stack<TreeNode> output = new Stack<TreeNode>();//第二个stack用于翻转第一个stack输出
    
    s.push(root);
    while(!s.isEmpty()){
        TreeNode cur = s.pop();
        output.push(cur); //把栈顶元素添加到第二个stack
        
        if(cur.left != null){
            s.push(cur.left);
        }
        if(cur.right != null){
            s.push(cur.right);
        }
        
        while(!output.isEmpty()){//遍历输出第二个stack,即为后序遍历
            System.out.print(output.pop().val + " ");
        }
    } 
}


© 著作权归作者所有

十一11
粉丝 6
博文 80
码字总数 19784
作品 0
杭州
私信 提问
LeetCode算法题-Merge Two Binary Trees(Java实现)

这是悦乐书的第274次更新,第290篇原创 01 看题和准备 今天介绍的是LeetCode算法题中Easy级别的第142题(顺位题号是617)。提供两个二叉树,将其合并为新的二叉树,也可以在其中一个二叉树上...

小川94
03/12
0
0
轻松搞定面试中的二叉树题目

求二叉树中的节点个数 2. 求二叉树的深度 3. 前序遍历,中序遍历,后序遍历 4.分层遍历二叉树(按层次从上往下,从左往右) 5. 将二叉查找树变为有序的双向链表 6. 求二叉树第K层的节点个数 ...

亚特兰缇斯
2015/09/10
185
0
python实现二叉树的遍历以及基本操作

主要内容: 二叉树遍历(先序、中序、后序、宽度优先遍历)的迭代实现和递归实现; 二叉树的深度,二叉树到叶子节点的所有路径; 首先,先定义二叉树类(python3),代码如下:

pandaWaKaKa
06/25
0
0
leetcode树专题894.897,919,951

满二叉树是一类二叉树,其中每个结点恰好有 0 或 2 个子结点。 返回包含 个结点的所有可能满二叉树的列表。 答案的每个元素都是一个可能树的根结点。 答案中每个树的每个都必须有 。 你可以按...

hui灰灰
2018/12/21
0
0
二叉树常见面试题

树是一种比较重要的数据结构,尤其是二叉树。二叉树是一种特殊的树,在二叉树中每个节点最多有两个子节点,一般称为左子节点和右子节点(或左孩子和右孩子),并且二叉树的子树有左右之分,其...

笨拙的小Q
2016/09/22
65
0

没有更多内容

加载失败,请刷新页面

加载更多

OSChina 周六乱弹 —— 早上儿子问我他是怎么来的

Osc乱弹歌单(2019)请戳(这里) 【今日歌曲】 @凉小生 :#今日歌曲推荐# 少点戾气,愿你和这个世界温柔以待。中岛美嘉的单曲《僕が死のうと思ったのは (曾经我也想过一了百了)》 《僕が死の...

小小编辑
今天
1K
13
Excption与Error包结构,OOM 你遇到过哪些情况,SOF 你遇到过哪些情况

Throwable 是 Java 中所有错误与异常的超类,Throwable 包含两个子类,Error 与 Exception 。用于指示发生了异常情况。 Java 抛出的 Throwable 可以分成三种类型。 被检查异常(checked Exc...

Garphy
今天
15
0
计算机实现原理专题--二进制减法器(二)

在计算机实现原理专题--二进制减法器(一)中说明了基本原理,现准备说明如何来实现。 首先第一步255-b运算相当于对b进行按位取反,因此可将8个非门组成如下图的形式: 由于每次做减法时,我...

FAT_mt
昨天
6
0
好程序员大数据学习路线分享函数+map映射+元祖

好程序员大数据学习路线分享函数+map映射+元祖,大数据各个平台上的语言实现 hadoop 由java实现,2003年至今,三大块:数据处理,数据存储,数据计算 存储: hbase --> 数据成表 处理: hive --> 数...

好程序员官方
昨天
7
0
tabel 中含有复选框的列 数据理解

1、el-ui中实现某一列为复选框 实现多选非常简单: 手动添加一个el-table-column,设type属性为selction即可; 2、@selection-change事件:选项发生勾选状态变化时触发该事件 <el-table @sel...

everthing
昨天
6
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部