Oliver's Blog
Search
K
Comment on page

Binary Tree Inorder Traversal

ID: 94; easy

Solution 1 (Go)

/**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
func inorderTraversal(root *TreeNode) []int {
result := make([]int, 0)
inorderHelper(root, &result)
return result
}
func inorderHelper(root *TreeNode, res *[]int) {
if root != nil {
inorderHelper(root.Left, res)
*res = append(*res, root.Val)
inorderHelper(root.Right, res)
}
}

Solution 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: A Tree
* @return: Inorder in ArrayList which contains node values.
*/
public List<Integer> inorderTraversal(TreeNode root) {
List<Integer> result = new ArrayList<>();
if (root == null) return result;
inorderTraversalHelper(root, result);
return result;
}
private void inorderTraversalHelper(TreeNode root, List<Integer> result) {
if (root == null) return;
inorderTraversalHelper(root.left, result);
inorderTraversalHelper(root.right, result);
}
}

Notes

• Recursion / Divide and conquer

Solution 3 (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: A Tree
* @return: Inorder in ArrayList which contains node values.
*/
public List<Integer> inorderTraversal(TreeNode root) {
List<Integer> result = new ArrayList<>();
Deque<TreeNode> stack = new ArrayDeque<>();
TreeNode curr = root;
while (curr != null || !stack.isEmpty()) {
while (curr != null) {
stack.push(curr);
curr = curr.left;
}
curr = stack.pop();