LC address: https://leetcode.com/problems/binary-tree-inorder-traversal/
Given a binary tree, return the inorder traversal of its nodes’ values.
For example:
Given binary tree [1,null,2,3]
,
1 \ 2 / 3
return [1,3,2]
.
Analysis:
基本的stack的运用(或者用recursion)。
Solution:
/** * 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 inorderTraversal(TreeNode root) { ArrayList list = new ArrayList(); Stack stack = new Stack(); TreeNode cur = root; while(!stack.empty() || cur != null){ if (cur != null) { stack.push(cur); cur = cur.left; } else { cur = stack.pop(); list.add(cur.val); cur = cur.right; } } return list; } }
Solution code can also be found here: https://github.com/all4win/LeetCode.git
One comment