专栏首页大白技术控的技术自留地C++版 - LeetCode 144. Binary Tree Preorder Traversal (二叉树先根序遍历,非递归)

C++版 - LeetCode 144. Binary Tree Preorder Traversal (二叉树先根序遍历,非递归)

144. Binary Tree Preorder Traversal

提交网址: https://leetcode.com/problems/binary-tree-preorder-traversal/

Total Accepted: 118355 Total Submissions: 297596 Difficulty: Medium

Given a binary tree, return the preorder traversal of its nodes' values.

For example: Given binary tree {1,#,2,3},

   1
    \
     2
    /
   3

return [1,2,3].

Note: Recursive solution is trivial, could you do it iteratively?

分析:

借助栈实现非递归先序遍历算法的方法如下: 1)将二叉树的根结点作为当前结点。 2)若当前结点非空,则先访问该结点,并将该结点进栈,再将其左孩子结点作为当前结点,重复步骤2),直到当前结点为NULL为止。 3)若栈非空,则栈顶结点出栈,并将当前结点的右孩子结点作为当前结点。 4)重复步骤2)、3),直到栈为空且当前结点为NULL为止。

AC代码:

#include<iostream>
#include<vector>
#include<stack>
using namespace std;
struct TreeNode
{
	int val;
	TreeNode *left, *right;
	TreeNode(int x): val(x), left(NULL), right(NULL) {} 
};

class Solution
{
public:
	vector<int> preorderTraversal(TreeNode *root)
	{
	vector<int> res;
	TreeNode *p;
	stack<TreeNode*> s;
	p=root;
	
	while(!s.empty() || p!=NULL)
	{
		if(p!=NULL)
		{
			res.push_back(p->val);
			s.push(p);
			p=p->left;
		}
		if(p==NULL)
		{
			p=s.top();
			s.pop();
			p=p->right;
		}
	}
	return res; 
}	
};

// 以下为测试部分
/*
int main()
{
	Solution sol;
	vector<int> res;
	
	TreeNode *root = new TreeNode(1); 
    root->right = new TreeNode(2); 
    root->right->left = new TreeNode(3); 
	
	res=sol.preorderTraversal(root);
	
	for(int i:res)
		cout<<i<<" ";  // 此处为vector遍历的方法,C++11标准支持 
	return 0;
}
*/

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • C++版 - LeetCode 145: Binary Tree Postorder Traversal(二叉树的后序遍历,迭代法)

    Total Accepted: 96378 Total Submissions: 271797 Difficulty: Hard

    Enjoy233
  • C++版 - 剑指offer 面试题63:二叉搜索树的第k个结点(二叉树中序遍历的应用) 题解

    题目:给定一颗二叉搜索树,请找出其中的第k大的结点。例如, 5 / \ 3 7 /\ /\ 2 4 6 8 (见下面的图1) 中,按结点数值大小顺序第三个结点的...

    Enjoy233
  • C++版 - 剑指offer 面试题39:判断平衡二叉树(LeetCode 110. Balanced Binary Tree) 题解

    提交网址:  http://www.nowcoder.com/practice/8b3b95850edb4115918ecebdf1b4d222?tpId=13...

    Enjoy233
  • 基于repmgr的postgresql主备高可用方案

    本文比较基础,主要介绍postgresql开源高可用工具repmgr的部署和使用,初学者可以根据本文步骤一步一步做下去,废话不多说,直接进入主题,本文以两台机器...

    数据库架构之美
  • 利用Zookeeper实现分布式锁及服务注册中心

    对于Zookeeper的定义以及原理,网上已经有很多的优秀文章对其进行了详细的介绍,所以本文不再进行这方面的阐述。 本文主要介绍一些基本的准备工作以及zooke...

    蓝夏
  • 29.C++- 异常处理

    C++内置了异常处理的语法元素 try catch try语句处理正常代码逻辑 当try语句发现异常时,则通过throw语句抛出异常,并退出try语句 catc...

    张诺谦
  • 通过saml统一身份认证登录腾讯云控制台实战

    saml全称:Security Assertion Markup Language,中文叫法是安全断言标记语言。首先,它是一种XML格式的语言;然后,它...

    文达
  • SpringBoot 统一时区的方案

    思路为: 将数据库和服务器的时间都采用标准时区UTC存储处理。前端拿到标准时区的数据,统一根据用户所在时区进行转换。这样保证了后端数据时区的一致性,前端根据实...

    飞奔去旅行
  • 360校招实习面经

    笔试完成不久就邮件通知结果了,安排了视频面试。 形式 视频面试 岗位 数据开发(大数据) 一面-技术 在牛客的视频面试平台。上午11:20,一面面试官(男)迟到...

    牛客网
  • 友元函数和友元类

    友元提供了不同类的成员函数之间、类的成员函数与一般函数之间进行数据共享的机制。通过友元,一个不同函数或另一个类中的成员函数可以访问类中的私有成员和保护成员。c+...

    chenjx85

扫码关注云+社区

领取腾讯云代金券