Binary Tree Preorder Traversal

Question

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

Note
Given binary tree {1,#,2,3},

1
\
2
/
3

return [1,2,3].

Example
Challenge
Can you do it without recursion?


題解1 - 遞迴

Python - Divide and Conquer

"""
Definition of TreeNode:
class TreeNode:
def __init__(self, val):
this.val = val
this.left, this.right = None, None
"""

class Solution:
"""
@param root: The root of binary tree.
@return: Preorder in ArrayList which contains node values.
"""
def preorderTraversal(self, root):
if root == None:
return []
return [root.val] + self.preorderTraversal(root.left) \
+ self.preorderTraversal(root.right)


C++ - Divide and Conquer

/**
* Definition of TreeNode:
* class TreeNode {
* public:
*     int val;
*     TreeNode *left, *right;
*     TreeNode(int val) {
*         this->val = val;
*         this->left = this->right = NULL;
*     }
* }
*/

class Solution {
public:
/**
* @param root: The root of binary tree.
* @return: Preorder in vector which contains node values.
*/
vector<int> preorderTraversal(TreeNode *root) {
vector<int> result;
if (root != NULL) {
// Divide (分)
vector<int> left = preorderTraversal(root->left);
vector<int> right = preorderTraversal(root->right);
// Merge
result.push_back(root->val);
result.insert(result.end(), left.begin(), left.end());
result.insert(result.end(), right.begin(), right.end());
}

return result;
}
};


C++ - Traversal

/**
* Definition of TreeNode:
* class TreeNode {
* public:
*     int val;
*     TreeNode *left, *right;
*     TreeNode(int val) {
*         this->val = val;
*         this->left = this->right = NULL;
*     }
* }
*/

class Solution {
public:
/**
* @param root: The root of binary tree.
* @return: Preorder in vector which contains node values.
*/
vector<int> preorderTraversal(TreeNode *root) {
vector<int> result;
traverse(root, result);

return result;
}

private:
void traverse(TreeNode *root, vector<int> &ret) {
if (root != NULL) {
ret.push_back(root->val);
traverse(root->left, ret);
traverse(root->right, ret);
}
}
};


Java - Divide and Conquer

/**
* Definition for a binary tree node.
* public class TreeNode {
*     int val;
*     TreeNode left;
*     TreeNode right;
*     TreeNode(int x) { val = x; }
* }
*/
public class Solution {
public List<Integer> preorderTraversal(TreeNode root) {
List<Integer> result = new ArrayList<Integer>();
if (root != null) {
// Divide
List<Integer> left = preorderTraversal(root.left);
List<Integer> right = preorderTraversal(root.right);
// Merge
}

return result;
}
}


題解2 - 迭代

Python

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
# @param {TreeNode} root
# @return {integer[]}
def preorderTraversal(self, root):
if root is None:
return []

result = []
s = []
s.append(root)
while s:
root = s.pop()
result.append(root.val)
if root.right is not None:
s.append(root.right)
if root.left is not None:
s.append(root.left)

return result


C++

/**
* Definition of TreeNode:
* class TreeNode {
* public:
*     int val;
*     TreeNode *left, *right;
*     TreeNode(int val) {
*         this->val = val;
*         this->left = this->right = NULL;
*     }
* }
*/

class Solution {
public:
/**
* @param root: The root of binary tree.
* @return: Preorder in vector which contains node values.
*/
vector<int> preorderTraversal(TreeNode *root) {
vector<int> result;
if (root == NULL) return result;

stack<TreeNode *> s;
s.push(root);
while (!s.empty()) {
TreeNode *node = s.top();
s.pop();
result.push_back(node->val);
if (node->right != NULL) {
s.push(node->right);
}
if (node->left != NULL) {
s.push(node->left);
}
}

return result;
}
};


Java

/**
* Definition for a binary tree node.
* public class TreeNode {
*     int val;
*     TreeNode left;
*     TreeNode right;
*     TreeNode(int x) { val = x; }
* }
*/
public class Solution {
public List<Integer> preorderTraversal(TreeNode root) {
List<Integer> result = new ArrayList<Integer>();
if (root == null) return result;

Stack<TreeNode> s = new Stack<TreeNode>();
s.push(root);
while (!s.empty()) {
TreeNode node = s.pop();
if (node.right != null) s.push(node.right);
if (node.left != null) s.push(node.left);
}

return result;
}
}


源碼分析

1. 對root進行異常處理
2. 將root壓入堆疊
3. 循環終止條件為堆疊s為空，所有元素均已處理完
4. 訪問當前堆疊頂元素(首先取出堆疊頂元素，隨後pop掉堆疊頂元素)並存入最終結果
5. 將右、左節點分別壓入堆疊內，以便取元素時為先左後右。
6. 返回最終結果