Leetcode: Binary Tree Preorder Traversal(二叉树前序遍历)

题目: 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?

二叉树的前序遍历

先看递归的写法(C++):

/**
 * Definition for binary tree
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution
{
private:
    vector<int> result;
public:
    vector<int> preorderTraversal(TreeNode *root)
    {
        if (root)
        {
            result.push_back(root->val);
            preorderTraversal(root->left);
            preorderTraversal(root->right);
        }
        return result;
    }
};

二叉树的中序遍历每次都是走树的左分支(left),直到左子树为空,然后开始从递归的最深处返回,访问右子树。所以得有一个结构存储左子树访问结束后回溯的那个节点从而进行右子书的访问。这个结构就是栈Stack。

/**
 * Definition for binary tree
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution
{
public:
    vector<int> preorderTraversal(TreeNode *root)
    {
        stack<TreeNode*> nodes;
        vector<int> result;
        TreeNode *node = root;
        while (node || !nodes.empty())
        {
            //一路向右
            if (node)
            {
                result.push_back(node->val);//先序遍历访问根节点
                nodes.push(node);//节点入栈
                node = node->left;
            }
            //右子树为空,追溯回最后的节点
            else
            {
                node = nodes.top();
                nodes.pop();//将此节点出栈
                node = node->right;//指向此节点的右节点,将该节点当成根节点循环
            }
        }
        return result;
    }
};

C#代码:

/**
 * Definition for binary tree
 * public class TreeNode {
 *     public int val;
 *     public TreeNode left;
 *     public TreeNode right;
 *     public TreeNode(int x) { val = x; }
 * }
 */
public class Solution
{
    public IList<int> PreorderTraversal(TreeNode root)
    {
        IList<int> result = new List<int>();
        Stack<TreeNode> nodes = new Stack<TreeNode>();
        TreeNode node = root;
        while (node != null || nodes.Count > 0)
        {
            if (node != null)
            {
                result.Add(node.val);
                nodes.Push(node);
                node = node.left;
            }
            else
            {
                node = nodes.Pop();
                node = node.right;
            }

        }
        return result;
    }
}

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

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏五分钟学算法

懵逼树上懵逼果:学习二分搜索树

我们通过两组添加元素,三组删除元素,一组查找元素的操作来理解二叉查找树的属性性质。

27110
来自专栏自学笔记

Data Structure前情提要——二叉树红黑树

叶子节点就是左右孩子都是空的,但是并不是每一颗树都像上图所示的那样这么规整,有些树树可以只有左孩子没有右孩子的。二叉树的节点一定会大于左节点的值小于右节点的值,...

13330
来自专栏五分钟学算法

【图解数据结构】 一组动画彻底理解插入排序

由于LeetCode上的算法题很多涉及到一些基础的数据结构,为了更好的理解后续更新的一些复杂题目的动画,推出一个新系列 -----《图解数据结构》,主要使用动画...

14030
来自专栏五分钟学算法

【图解数据结构】 一组动画彻底理解二叉树遍历

定义:二叉树的遍历是指从根结点出发,按照某种次序依次访问二叉树中所有结点,使得每个结点被访问一次且仅被访问一次。

26210
来自专栏wym

PTA 7-14 电话聊天狂人 二叉搜索树

输入首先给出正整数N(≤10^​5​​),为通话记录条数。随后N行,每行给出一条通话记录。简单起见,这里只列出拨出方和接收方的11位数字构成的手机号码,其中以空...

10920
来自专栏牛客网

秋招算法岗面经(主要是撸代码题)

如果你以后想起,无论何时回想起来,这件事都会让你嘴角带笑的话,你就去做吧。但如果你并不这么认为或者不太确定,那就忘掉它吧,因为你还有大把时间。——《完美陌生人》

21810
来自专栏五分钟学算法

每天一算:二叉树的中序遍历

下面这种写法使用了一个辅助结点p,这种写法其实可以看作是一个模版,对应的还有前序和后序的模版写法,形式很统一,方便于记忆。上篇更新前序的和后面要更新后序文章中都...

12020
来自专栏iOS开发攻城狮的集散地

数据结构与算法 - 查找

16530
来自专栏五分钟学算法

图解LeetCode第 199 号问题:二叉树的右视图

14020
来自专栏流浪猫的golang

golang 堆排序

23230

扫码关注云+社区

领取腾讯云代金券

年度创作总结 领取年终奖励