文档章节

144. 二叉树的前序遍历

o
 osc_a22drz29
发布于 2019/03/26 17:58
字数 291
阅读 3
收藏 0

给定一个二叉树,返回它的 前序 遍历。

 示例:

输入: [1,null,2,3]  
   1
    \
     2
    /
   3 

输出: [1,2,3]

进阶: 递归算法很简单,你可以通过迭代算法完成吗?

思路:方法一:采用二叉搜索树的前序遍历,先判断节点是否为空,为空则返回list,不为空,则将节点的val存入list,继续遍历节点的左子节点和右子节点,依次进行得到最终结果。

   方法二:采用借助栈数据结构的非递归方法。

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public List<Integer> preorderTraversal(TreeNode root) {
        ArrayList<Integer> list = new ArrayList<Integer>();
        //方法一:采用递归遍历,测试用例执行速度快
        //if(root==null)
        //    return list;
        //return preorder(root,list);
        
        //方法二:借用栈数据结构的非递归遍历,测试用例执行速度慢
        Stack<TreeNode> stack = new Stack();
        if(root==null) return list;
        
        stack.push(root);
        while(!stack.isEmpty()){
            root = stack.pop();
            if(root!=null)
                list.add(root.val);
            if(root.right!=null)
                stack.push(root.right);
            if(root.left!=null)
                stack.push(root.left);
        }
        return list;
    }
    
    private ArrayList<Integer> preorder(TreeNode node,ArrayList<Integer> list){
        if(node==null)
            return list;
        
        list.add(node.val);
        list = preorder(node.left,list);
        list = preorder(node.right,list);
        return list;
    }
}

 

o
粉丝 0
博文 500
码字总数 0
作品 0
私信 提问
加载中
请先登录后再评论。

暂无文章

OSChina 周五乱弹 —— 你大妈还是你大妈

Osc乱弹歌单(2020)请戳(这里) 【今日歌曲】 @watergood:是时候分享一波我的这张纯音乐歌单了,过去的五年多时间里,我陆陆续续地把听到的好听的纯音乐添加了进去,目前一共65首,相信总...

小小编辑
今天
19
0
在Objective-C中生成随机数 - Generating random numbers in Objective-C

问题: I'm a Java head mainly, and I want a way to generate a pseudo-random number between 0 and 74. In Java I would use the method: 我主要是Java头,我想要一种生成0到74之间的伪随......

技术盛宴
今天
13
0
ftp-ftps-sftp的关系

Ftp FTP 是File Transfer Protocol(文件传输协议)的英文简称,而中文简称为“文传协议”。用于Internet上的控制文件的双向传输。同时,它也是一个应用程序(Application)。基于不同的操作...

独钓渔
今天
12
0
使Vim将所有空格显示为字符 - Make Vim show ALL white spaces as a character

问题: I can't find a way to make Vim show all white spaces as a character. 我找不到让Vim将所有空白显示为字符的方法。 All I found was about tabs, trailing spaces etc. 我发现的只......

富含淀粉
今天
23
0
RN 接入高德地图遇到的一些问题

react-native-amap-geolocation、react-native-amap3d 1、iOS Geolocation.getCurrentPosition 获取坐标后,没有返回 address 信息? 逆地理编码 Android 默认返回逆地理编码,而 iOS 需要手...

Jack088
今天
14
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部