Binary Tree Inorder Traversal(转)

 

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

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

   1
    \
     2
    /
   3

 

return [1,3,2].

 

Java代码 

 

  1. /** 
  2.  * Definition for a binary tree node. 
  3.  * public class TreeNode { 
  4.  *     int val; 
  5.  *     TreeNode left; 
  6.  *     TreeNode right; 
  7.  *     TreeNode(int x) { val = x; } 
  8.  * } 
  9.  */  
  10. public class Solution {  
  11.     public List<Integer> inorderTraversal(TreeNode root) {  
  12.         List<Integer> res = new ArrayList<>();  
  13.         dfs(root, res);  
  14.         return res;  
  15.     }  
  16.   
  17.     private void dfs(TreeNode root, List<Integer> res) {  
  18.         if (root != null) {  
  19.             dfs(root.left, res);  
  20.             res.add(root.val);  
  21.             dfs(root.right, res);  
  22.         }  
  23.     }  
  24. }  

 

Java代码 

 

  1. /** 
  2.  * Definition for a binary tree node. 
  3.  * public class TreeNode { 
  4.  *     int val; 
  5.  *     TreeNode left; 
  6.  *     TreeNode right; 
  7.  *     TreeNode(int x) { val = x; } 
  8.  * } 
  9.  */  
  10. public class Solution {  
  11.     public List<Integer> inorderTraversal(TreeNode root) {  
  12.         List<Integer> res = new ArrayList<>();  
  13.         if (root == null) {  
  14.             return res;  
  15.         }  
  16.         LinkedList<TreeNode> stack = new LinkedList<>();  
  17.         while (root!=null || !stack.isEmpty()) {  
  18.             if (root!=null) {  
  19.                 stack.push(root);  
  20.                 root = root.left;  
  21.             } else {  
  22.                 root = stack.pop();  
  23.                 res.add(root.val);  
  24.                 root = root.right;  
  25.             }  
  26.         }  
  27.         return res;  
  28.     }  
  29. }  

http://hcx2013.iteye.com/blog/2230218

 

时间: 2024-09-15 00:14:43

Binary Tree Inorder Traversal(转)的相关文章

[LeetCode]94.Binary Tree Inorder Traversal

[题目] Given a binary tree, return the inorder traversal of its nodes' values. For example: Given binary tree {1,#,2,3}, 1 \ 2 / 3 return [1,3,2]. Note: Recursive solution is trivial, could you do it iteratively? confused what "{1,#,2,3}" means? &

[LeetCode]144.Binary Tree Preorder Traversal

[题目] Given a binary tree, return the preorder traversal of its nodes' values. For example: Given binary tree {1,#,2,3}, 1 \ 2 / 3 return [1,2,3]. Note: Recursive solution is trivial, could you do it iteratively? [代码一] /*******************************

[LeetCode 第8题] -- Binary Tree Preorder Traversal

题目链接: Binary Tree Preorder Traversal 题目意思: 给定一个二叉树根节点,求前序序列 代码: /** * Definition for binary tree * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */ class Solution { publi

[LeetCode] Binary Tree Preorder Traversal

Given a binary tree, return the preorder traversal of its nodes' values. For example: Given binary tree {1,#,2,3}, return [3,2,1]. Note: Recursive solution is trivial, could you do it iteratively? 递归实现代码 /*********************************************

[LeetCode]145.Binary Tree Postorder Traversal

[题目] Given a binary tree, return the postorder traversal of its nodes' values. For example: Given binary tree {1,#,2,3}, 1 \ 2 / 3 return [3,2,1]. Note: Recursive solution is trivial, could you do it iteratively? [代码] /*******************************

Binary Tree Preorder Traversal

Given a binary tree, return the preorder traversal of its nodes' values. For example:Given binary tree {1,#,2,3}, 1 \ 2 / 3   return [1,2,3]. 二叉树前序遍历的非递归版本,C++实现代码: #include<iostream> #include<new> #include<vector> #include<stack>

[LeetCode 第12题] -- Binary Tree Postorder Traversal

题目链接: Binary Tree PostOrder Trveral 题目意思: 给定一棵二叉树,求后续遍历序列 代码: /** * Definition for binary tree * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */ class Solution { public:

[LeetCode]*105.Construct Binary Tree from Preorder and Inorder Traversal

题目 Given preorder and inorder traversal of a tree, construct the binary tree. Note: You may assume that duplicates do not exist in the tree. 思路 主要是根据前序遍历和中序遍历的特点解决这个题目. 1.确定树的根节点.树根是当前树中所有元素在前序遍历中最先出现的元素. 2.求解树的子树.找出根节点在中序遍历中的位置,根左边的所有元素就是左子树,根右边的所有元

[LeetCode]*106.Construct Binary Tree from Inorder and Postorder Traversal

题目 Given inorder and postorder traversal of a tree, construct the binary tree. Note: You may assume that duplicates do not exist in the tree. 思路 思路和[LeetCode]*105.Construct Binary Tree from Preorder and Inorder Traversal一样. 代码 /*---------------------