144. Binary Tree Preorder Traversal

发表于 | 分类于 | 阅读次数
字数统计 322 | 阅读时长 2

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

1
2
3
4
5
6
7
8
9
For example :
Given binary tree{ 1,#,2,3 },

       1
        \
          2
         /
       3
return[1, 2, 3].

题意：

　　二叉树的先根序遍历。

思路：

　方法一：

　　二叉树的先根序遍历递归实现。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
struct TreeNode {
	int val;
	TreeNode *left, *right;
	TreeNode(int x) :val(x), left(NULL), right(NULL) {}
};
//二叉树的先序遍历的递归形式
//递归操作：(递归操作就像栈存储数据一样，先进后出)
//思想：若二叉树为空，返回。否则   1）遍历根节点；2）先序遍历左子树；3）先序遍历右子树
class Solution
{
  vector<int>  resVals;
public:
    void preOrderRecursive(TreeNode *root) {
        if (!root)
        {
            return;
        }
        resVals.push_back(root->val);//遍历数据,放入结果集
        preOrderRecursive(root->left);//递归调用，先序遍历左子树  
        preOrderRecursive(root->right);//递归调用，先序遍历右子树  
    }  
};

　方法二：

　　二叉树的先根序遍历非递归实现,借助栈。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
class Solution
{
public:
    vector<int> preorderTraversal1(TreeNode* root) {
        vector<int> vals;
        if (!root)
        {
            return vals;
        }
        stack<TreeNode*> s;
      	TreeNode *tmp=root;
        while (tmp || !s.empty())
        {
          	if(tmp)
            {
                vals.push_back(tmp->val);
              	s.push(tmp);
              	tmp = tmp->left;
            }
          	else
            {
                tmp = s.top();
               	s.pop();
              	tmp = tmp->right;
            }
        }
        return vals;
    }
}；