Question

Source

• leetcode: Binary Tree Preorder Traversal | LeetCode OJ
• lintcode: (66) Binary Tree Preorder Traversal

Problem

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

Example

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

1
 \
  2
 /
3

return [1,2,3] .

Challenge

Can you do it without recursion?

题解 1 - 递归

面试时不推荐递归这种做法。

递归版很好理解，首先判断当前节点（根节点) 是否为 null ，是则返回空 vector，否则先返回当前节点的值，然后对当前节点的左节点递归，最后对当前节点的右节点递归。递归时对返回结果的处理方式不同可进一步细分为遍历和分治两种方法。

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
      result.add(root.val);
      result.addAll(left);
      result.addAll(right);
    }

    return result;
  }
}

源码分析

使用遍历的方法保存递归返回结果需要使用辅助递归函数 traverse ，将结果作为参数传入递归函数中，传值时注意应使用 vector 的引用。 分治方法首先分开计算各结果，最后合并到最终结果中。 C++ 中由于是使用 vector, 将新的 vector 插入另一 vector 不能再使用 push_back, 而应该使用 insert。 Java 中使用 addAll 方法。

复杂度分析

遍历树中节点，时间复杂度 O(n)O(n)O(n), 未使用额外空间。

题解 2 - 迭代

迭代时需要利用栈来保存遍历到的节点，纸上画图分析后发现应首先进行出栈抛出当前节点，保存当前节点的值，随后将右、左节点分别入栈（注意入栈顺序，先右后左)，迭代到其为叶子节点(NULL) 为止。

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;

    Deque<TreeNode> stack = new ArrayDeque<TreeNode>();
    stack.push(root);
    while (!stack.isEmpty()) {
      TreeNode node = stack.pop();
      result.add(node.val);

      if (node.right != null) stack.push(node.right);
      if (node.left != null) stack.push(node.left);
    }

    return result;
  }
}

源码分析

1. 对 root 进行异常处理
2. 将 root 压入栈
3. 循环终止条件为栈 s 为空，所有元素均已处理完
4. 访问当前栈顶元素（首先取出栈顶元素，随后 pop 掉栈顶元素) 并存入最终结果
5. 将右、左节点分别压入栈内，以便取元素时为先左后右。
6. 返回最终结果

其中步骤 4,5,6 为迭代的核心，对应前序遍历「根左右」。

所以说到底， 使用迭代，只不过是另外一种形式的递归。 使用递归的思想去理解遍历问题会容易理解许多。

复杂度分析

使用辅助栈，最坏情况下栈空间与节点数相等，空间复杂度近似为 O(n)O(n)O(n), 对每个节点遍历一次，时间复杂度近似为 O(n)O(n)O(n).