144. 二叉树的前序遍历
Given a binary tree, return the preorder traversal of its nodes’ values. 给定一棵二叉树，返回其节点值的前序遍历。 For example: Given binary tree [1,null,2,3],
1
\
2
/
3
return [1,2,3].
Note: Recursive solution is trivial, could you do it iteratively?
解法一：递归
/**
* Definition for a binary tree node.
* public class TreeNode {
* public int val;
* public TreeNode left;
* public TreeNode right;
* public TreeNode(int x) { val = x; }
* }
*/
using System;
using System.Collections.Generic;
public class Solution {
private List<
int> mResultList;
public IList<
int>
PreorderTraversal(TreeNode root) {
mResultList =
new List<
int>();
if(root ==
null){
return mResultList;
}
PreTraversal(root);
return mResultList;
}
private void PreTraversal(TreeNode currentRoot){
if(currentRoot ==
null){
return;
}
mResultList.Add(currentRoot.val);
PreTraversal(currentRoot.left);
PreTraversal(currentRoot.right);
}
}
解法二：迭代遍历，利用栈
/**
* Definition for a binary tree node.
* public class TreeNode {
* public int val;
* public TreeNode left;
* public TreeNode right;
* public TreeNode(int x) { val = x; }
* }
*/
using System;
using System.Collections.Generic;
public class Solution {
public IList<
int>
PreorderTraversal(TreeNode root) {
var resultList =
new List<
int>();
if(root ==
null){
return resultList;
}
var nodeStack =
new Stack<TreeNode>();
nodeStack.Push(root);
while(nodeStack.Count !=
0 ){
var tempNode = nodeStack.Pop();
if(tempNode.right !=
null){
nodeStack.Push(tempNode.right);
}
if(tempNode.left !=
null){
nodeStack.Push(tempNode.left);
}
resultList.Add(tempNode.val);
}
return resultList;
}
}
