題目：

二叉樹的中序遍歷

給出一棵二叉樹,返回其中序遍歷

樣例

給出二叉樹?{1,#,2,3},

1\2/3

返回?[1,3,2].

挑戰

你能使用非遞歸算法來實現么?

解題：

程序直接來源

Java程序：

/*** Definition of TreeNode:* public class TreeNode {* public int val;* public TreeNode left, right;* public TreeNode(int val) {* this.val = val;* this.left = this.right = null;* }* }*/ public class Solution {/*** @param root: The root of binary tree.* @return: Inorder in ArrayList which contains node values.*/public ArrayList<Integer> inorderTraversal(TreeNode root) {// write your code hereArrayList<TreeNode> p = new ArrayList<TreeNode>(); ArrayList<Integer> res = new ArrayList<Integer>(); while(root != null || p.size() != 0){ while(root != null){ p.add(root); root = root.left; } root = p.get(p.size()-1); p.remove(p.size()-1); res.add(root.val); root = root.right; } return res; }} View Code

總耗時:?1238?ms

Python程序：

""" Definition of TreeNode: class TreeNode:def __init__(self, val):self.val = valself.left, self.right = None, None """class Solution:"""@param root: The root of binary tree.@return: Inorder in ArrayList which contains node values."""def inorderTraversal(self, root):# write your code herep = [root] res = [0] while root is not None or len(p) != 1: while root is not None: p.append(root) root = root.left root = p[len(p)-1] del p[len(p)-1] res.append(root.val) root = root.right n = len(res) return res[1:n] View Code

總耗時:?263?ms

非遞歸程序，理解不透，還需要人丑就要多讀書

根據上面靈感，遞歸程序如下：

java程序：

/*** Definition of TreeNode:* public class TreeNode {* public int val;* public TreeNode left, right;* public TreeNode(int val) {* this.val = val;* this.left = this.right = null;* }* }*/ public class Solution {/*** @param root: The root of binary tree.* @return: Inorder in ArrayList which contains node values.*/public ArrayList<Integer> inorderTraversal(TreeNode root) {// write your code here ArrayList<Integer> res = new ArrayList<Integer>(); res = inorderTrun(res,root);return res; }public ArrayList<Integer> inorderTrun(ArrayList<Integer> res,TreeNode root){if(root == null)return res;if(root!=null){if(root.left!=null){res = inorderTrun(res,root.left);}res.add(root.val);if(root.right!=null){res = inorderTrun(res,root.right);}}return res;}} View Code

總耗時:?1714?ms

Python程序：

""" Definition of TreeNode: class TreeNode:def __init__(self, val):self.val = valself.left, self.right = None, None """class Solution:"""@param root: The root of binary tree.@return: Inorder in ArrayList which contains node values."""def inorderTraversal(self, root):# write your code hereres = []res = self.inorderTrun(res,root)return resdef inorderTrun(self,res,root):if root==None:return resif root.left!=None:res = self.inorderTrun(res,root.left)res.append(root.val)if root.right!=None:res = self.inorderTrun(res,root.right)return res View Code

總耗時:?213?ms

?根據上面的程序理解，可根據棧實現，上面定義的ArrayList也是起到棧的作用

?

總結

以上是生活随笔為你收集整理的lintcode：二叉树的中序遍历的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。