94. Binary Tree Inorder Traversal

[Shawngbk]

/**

• Definition for a binary tree node.
• public class TreeNode {
• int val;
• TreeNode left;
• TreeNode right;
• TreeNode(int x) { val = x; }
• } */

1.递归 public class Solution { List res = new ArrayList(); public List inorderTraversal(TreeNode root) { if(root == null) return res; if(root != null) helper(root); return res; }

private void helper(TreeNode root) {
    if(root.left != null)
    helper(root.left);

    res.add(root.val);

    if(root.right != null)
    helper(root.right);
}

}

———————————————————————————————————————— 2.stack

public List inorderTraversal(TreeNode root) { List res = new ArrayList(); if(root == null) return res; Stack helper = new Stack(); helper.push(root); while(!helper.isEmpty()) { TreeNode temp = helper.peek(); if(temp.left != null) { helper.push(temp.left); temp.left = null; } else { res.add(temp.val); helper.pop(); if(temp.right != null) { helper.push(temp.right); } } } return res; }

[Shawngbk]

http://www.programcreek.com/2012/12/leetcode-solution-of-binary-tree-inorder-traversal-in-java/

[Shawngbk]

Microsoft