澳门威利斯人_威利斯人娱乐「手机版」

来自 威利斯人娱乐 2019-11-16 06:11 的文章
当前位置: 澳门威利斯人 > 威利斯人娱乐 > 正文

非递归的先序遍历

[LeetCode] Binary Tree Preorder Traversal (非递归的先序遍历卡塔 尔(阿拉伯语:قطر‎

 

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?

二. 标题深入分析

可使用递归解法,而只借使能用递归,约等于说能用栈来还原递归进程,由此方法不仅仅风流洒脱种。

行使栈来达成二叉树的遍历:首先在stack中压入当前的root,由于是前序遍历,故树是遵照先根,然后左子树和后右子树实行访问,故pop收取叁个结点,将它的value插手访谈连串。之后压入它的右子树和左子树。直到stack为空。

三. 示例代码

递归解法:

#include 
#include 

using namespace std;

struct TreeNode
{
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(NULL), right(NULL){}
};

class Solution
{
public:
    void preorder(TreeNode *root, vector &k)
    {
        if (root != NULL)
        {
        k.push_back(root->val);
        preorder(root->left, k);
        preorder(root->right, k);
        }
    }

    vector preorderTraversal(TreeNode *root)
    {
        vector temp;
        preorder(root, temp);
        return temp;
    }
};

非递归解法(stack达成卡塔尔国:

#include 
#include 
#include 

using namespace std;

struct TreeNode
{
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(NULL), right(NULL){}
};

class Solution {
public:
    vector preorderTraversal(TreeNode *root) {
        vector temp;
        temp.clear();
        stack k;
        if (root == NULL)
            return temp;
        k.push(root);
        while (!k.empty())
        {
            TreeNode *node = k.top();
            k.pop();
            temp.push_back(node->val);
            if (node->right != NULL)
                k.push(node->right);
            if (node->left != NULL)
                k.push(node->left);
        }
        return temp;
    }
};

 

Tree Preorder Traversal 风姿罗曼蒂克. 标题陈述 Given a binary tree, return the preorder traversal of its nodes values. For example: Given binary tree {1,#,2,3} ,...

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?

 


 

 

Solution:

递归解法很简短:

 1 # Definition for a binary tree node.
 2 # class TreeNode:
 3 #     def __init__(self, x):
 4 #         self.val = x
 5 #         self.left = None
 6 #         self.right = None
 7 
 8 class Solution:
 9     # @param {TreeNode} root
10     # @return {integer[]}
11     def preorderTraversal(self, root):
12         if root == None:
13             return []
14         else:
15             return [root.val]   self.preorderTraversal(root.left)   self.preorderTraversal(root.right)

迭代版本也是符合规律的将递归改成迭代的本子:

用叁个栈来模拟递归的进程,注意栈 FILO 的特征。所以,对于当前根,要把右子树先插足栈,然后再把左子树参加栈。

前序遍历的次第是:根 - 左子树 - 右子树。

代码如下:

 1 # Definition for a binary tree node.
 2 # class TreeNode:
 3 #     def __init__(self, x):
 4 #         self.val = x
 5 #         self.left = None
 6 #         self.right = None
 7 
 8 class Solution:
 9     # @param {TreeNode} root
10     # @return {integer[]}
11     def preorderTraversal(self, root):
12         stack = []
13         path = []
14         if root != None:
15             stack.append(root)
16         while stack != []:
17             e = stack.pop()
18             path.append(e.val)
19             if e.right != None:
20                 stack.append(e.right)
21             if e.left != None:
22                 stack.append(e.left)
23         return path

 

本文由澳门威利斯人发布于威利斯人娱乐,转载请注明出处:非递归的先序遍历

关键词: 澳门威利斯人 算法与数据