Binary Tree Preorder Traversal · 數據結構與算法/leetcode/lintcode題解

# Binary Tree Preorder Traversal ### Source - leetcode: [Binary Tree Preorder Traversal | LeetCode OJ](https://leetcode.com/problems/binary-tree-preorder-traversal/) - lintcode: [(66) Binary Tree Preorder Traversal](http://www.lintcode.com/en/problem/binary-tree-preorder-traversal/) ~~~ 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 - 遞歸 **面試時不推薦遞歸這種做法。** 遞歸版很好理解，首先判斷當前節點(根節點)是否為`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; Stack<TreeNode> s = new Stack<TreeNode>(); s.push(root); while (!s.empty()) { TreeNode node = s.pop(); result.add(node.val); if (node.right != null) s.push(node.right); if (node.left != null) s.push(node.left); } return result; } } ~~~ ### 源碼分析 1. 對root進行異常處理 1. 將root壓入棧 1. 循環終止條件為棧s為空，所有元素均已處理完 1. 訪問當前棧頂元素(首先取出棧頂元素，隨后pop掉棧頂元素)并存入最終結果 1. 將右、左節點分別壓入棧內，以便取元素時為先左后右。 1. 返回最終結果其中步驟4,5,6為迭代的核心，對應前序遍歷「根左右」。所以說到底，**使用迭代，只不過是另外一種形式的遞歸。**使用遞歸的思想去理解遍歷問題會容易理解許多。 ### 復雜度分析使用輔助棧，最壞情況下棧空間與節點數相等，空間復雜度近似為 O(n)O(n)O(n), 對每個節點遍歷一次，時間復雜度近似為 O(n)O(n)O(n).