【LintCode 题解】腾讯算法面试题：二叉树的前序遍历

题目描述

给出一棵二叉树，返回其节点值的前序遍历。

• 首个数据为根节点，后面接着是其左儿子和右儿子节点值，"#"表示不存在该子节点。

• 节点数量不超过20

样例 1:

  

   

    

     

    
    

     

      输入：{1,2,3}
     
    
   

    

     

    
    

     

      输出：[1,2,3]
     
    
   

    

     

    
    

     

      解释：
     
    
   

    

     

    
    

     

         1
     
    
   

    

     

    
    

     

        / \
     
    
   

    

     

    
    

     

       2   3
     
    
   

    

     

    
    

     

      它将被序列化为{1,2,3}
     
    
   

    

     

    
    

     

      前序遍历
     
    
  

样例 2:

  

   

    

     

    
    

     

      输入：{
      1,
      #,2,3}
     
    
   

    

     

    
    

     

      输出：[
      1,
      2,
      3]
     
    
   

    

     

    
    

     

      解释：
     
    
   

    

     

    
    

     

      1
     
    
   

    

     

    
    

     

       \
     
    
   

    

     

    
    

     
  
      2
     
    
   

    

     

    
    

     

       /
     
    
   

    

     

    
    

     

      3
     
    
   

    

     

    
    

     

      它将被序列化为{
      1,
      #,2,3}
     
    
   

    

     

    
    

     

      前序遍历
     
    
  

题解

非递归方式实现前序遍历时，首先存入当前节点值，然后先将右儿子压入栈中，再将左儿子压入栈中。对栈中元素遍历访问。

国内大厂面试除了操作系统和计算机网络这些基础外，还需要熟练掌握算法和数据结构。自己刷题来准备的话至少需要3个月的时间，当然通过算法课程，一般能节省大把时间，快的话一个月时间就能应对大厂算法面试。

  

   

    

     

    
    

     

      Version 
      0: Non-Recursion (Recommend)
     
    
   

    

     

    
    

     

      /**
     
    
   

    

     

    
    

     

       * Definition for binary tree
     
    
   

    

     

    
    

     

       * public class TreeNode {
     
    
   

    

     

    
    

     

       * int val;
     
    
   

    

     

    
    

     

       * TreeNode left;
     
    
   

    

     

    
    

     

       * TreeNode right;
     
    
   

    

     

    
    

     

       * TreeNode(int x) { val = x; }
     
    
   

    

     

    
    

     

       * }
     
    
   

    

     

    
    

     

       */
     
    
   

    

     

    
    

     

      public 
      class Solution {
     
    
   

    

     

    
    

     
    
      public List<Integer> preorderTraversal(TreeNode root) {
     
    
   

    

     

    
    

     

              Stack<TreeNode> stack = 
      new Stack<TreeNode>();
     
    
   

    

     

    
    

     

              List<Integer> preorder = 
      new ArrayList<Integer>();
     
    
   

    

     

    
    

     
        
     
    
   

    

     

    
    

     
        
      if (root == 
      null) {
     
    
   

    

     

    
    

     
            
      return preorder;
     
    
   

    

     

    
    

     

              }
     
    
   

    

     

    
    

     
        
     
    
   

    

     

    
    

     

              stack.push(root);
     
    
   

    

     

    
    

     
        
      while (!stack.empty()) {
     
    
   

    

     

    
    

     

                  TreeNode node = stack.pop();
     
    
   

    

     

    
    

     

                  preorder.add(node.val);
     
    
   

    

     

    
    

     
            
      if (node.right != 
      null) {
     
    
   

    

     

    
    

     

                      stack.push(node.right);
     
    
   

    

     

    
    

     

                  }
     
    
   

    

     

    
    

     
            
      if (node.left != 
      null) {
     
    
   

    

     

    
    

     

                      stack.push(node.left);
     
    
   

    

     

    
    

     

                  }
     
    
   

    

     

    
    

     

              }
     
    
   

    

     

    
    

     
        
     
    
   

    

     

    
    

     
        
      return preorder;
     
    
   

    

     

    
    

     

          }
     
    
   

    

     

    
    

     

      }
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     

      //Version 1: Traverse
     
    
   

    

     

    
    

     

      public 
      class Solution {
     
    
   

    

     

    
    

     
    
      public ArrayList<Integer> preorderTraversal(TreeNode root) {
     
    
   

    

     

    
    

     

              ArrayList<Integer> result = 
      new ArrayList<Integer>();
     
    
   

    

     

    
    

     

              traverse(root, result);
     
    
   

    

     

    
    

     
        
      return result;
     
    
   

    

     

    
    

     

          }
     
    
   

    

     

    
    

     
    
      // 把root为跟的preorder加入result里面
     
    
   

    

     

    
    

     
    
      private void traverse(TreeNode root, ArrayList<Integer> result) {
     
    
   

    

     

    
    

     
        
      if (root == 
      null) {
     
    
   

    

     

    
    

     
            
      return;
     
    
   

    

     

    
    

     

              }
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     

              result.add(root.val);
     
    
   

    

     

    
    

     

              traverse(root.left, result);
     
    
   

    

     

    
    

     

              traverse(root.right, result);
     
    
   

    

     

    
    

     

          }
     
    
   

    

     

    
    

     

      }
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     

      //Version 2: Divide & Conquer
     
    
   

    

     

    
    

     

      public 
      class Solution {
     
    
   

    

     

    
    

     
    
      public ArrayList<Integer> preorderTraversal(TreeNode root) {
     
    
   

    

     

    
    

     

              ArrayList<Integer> result = 
      new ArrayList<Integer>();
     
    
   

    

     

    
    

     
        
      // null or leaf
     
    
   

    

     

    
    

     
        
      if (root == 
      null) {
     
    
   

    

     

    
    

     
            
      return result;
     
    
   

    

     

    
    

     

              }
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     
        
      // Divide
     
    
   

    

     

    
    

     

              ArrayList<Integer> left = preorderTraversal(root.left);
     
    
   

    

     

    
    

     

              ArrayList<Integer> right = preorderTraversal(root.right);
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     
        
      // Conquer
     
    
   

    

     

    
    

     

              result.add(root.val);
     
    
   

    

     

    
    

     

              result.addAll(left);
     
    
   

    

     

    
    

     

              result.addAll(right);
     
    
   

    

     

    
    

     
        
      return result;
     
    
   

    

     

    
    

     

          }
     
    
   

    

     

    
    

     

      }