LeetCode - Easy - 94. Binary Tree Inorder Traversal-蒲公英云

LeetCode - Easy - 94. Binary Tree Inorder Traversal

Bertha 。 2022-10-06 02:54 208阅读 0赞

Topic

Hash Table
Stack
Tree

Description

https://leetcode.com/problems/binary-tree-inorder-traversal/

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

Example 1:

Input: root = [1,null,2,3]
Output: [1,3,2]

Example 2:

Input: root = []
Output: []

Example 3:

Input: root = [1]
Output: [1]

Example 4:

Input: root = [1,2]
Output: [2,1]

Example 5:

Input: root = [1,null,2]
Output: [1,2]

Constraints:

The number of nodes in the tree is in the range [0, 100].
-100 <= Node.val <= 100

Follow up: Recursive solution is trivial, could you do it iteratively?

Analysis

方法一：递归法

方法二：迭代法

Submission

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import com.lun.util.BinaryTree.TreeNode;
public class BinaryTreeInorderTraversal { 
    //方法一：递归法
    public List<Integer> inorderTraversal(TreeNode root) { 
        List<Integer> result = new ArrayList<>();
        inorderTraversal(root, result);
        return result;
    }
    private void inorderTraversal(TreeNode node, List<Integer> result) { 
        if(node == null) return;
        inorderTraversal(node.left, result);
        result.add(node.val);
        inorderTraversal(node.right, result);
    }
    //方法二：迭代法
    public List<Integer> inorderTraversal2(TreeNode root) { 
        List<Integer> result = new ArrayList<>();
        if(root == null) return result;
        LinkedList<TreeNode> stack = new LinkedList<>();
        TreeNode p = root;
        while(!stack.isEmpty() || p != null) { 
            if(p != null) { 
                stack.push(p);
                p = p.left;
            }else { 
                TreeNode node = stack.pop();
                result.add(node.val);
                p = node.right;
            }
        }
        return result;
    }
}

Test

import static org.junit.Assert.*;
import org.hamcrest.collection.IsEmptyCollection;
import org.hamcrest.collection.IsIterableContainingInOrder;
import org.junit.Test;
import com.lun.util.BinaryTree;
public class BinaryTreeInorderTraversalTest { 
    @Test
    public void test() { 
        BinaryTreeInorderTraversal obj = new BinaryTreeInorderTraversal();
        assertThat(obj.inorderTraversal(BinaryTree.integers2BinaryTree(1,null,2,3)),// 
                IsIterableContainingInOrder.contains(1,3,2));
        assertThat(obj.inorderTraversal(null),//
                IsEmptyCollection.empty());
        assertThat(obj.inorderTraversal(BinaryTree.integers2BinaryTree(1)),// 
                IsIterableContainingInOrder.contains(1));
        assertThat(obj.inorderTraversal(BinaryTree.integers2BinaryTree(1, 2)),// 
                IsIterableContainingInOrder.contains(2, 1));
        assertThat(obj.inorderTraversal(BinaryTree.integers2BinaryTree(1, null, 2)),// 
                IsIterableContainingInOrder.contains(1, 2));
    }
    @Test
    public void test2() { 
        BinaryTreeInorderTraversal obj = new BinaryTreeInorderTraversal();
        assertThat(obj.inorderTraversal2(BinaryTree.integers2BinaryTree(1,null,2,3)),// 
                IsIterableContainingInOrder.contains(1,3,2));
        assertThat(obj.inorderTraversal2(null),//
                IsEmptyCollection.empty());
        assertThat(obj.inorderTraversal2(BinaryTree.integers2BinaryTree(1)),// 
                IsIterableContainingInOrder.contains(1));
        assertThat(obj.inorderTraversal2(BinaryTree.integers2BinaryTree(1, 2)),// 
                IsIterableContainingInOrder.contains(2, 1));
        assertThat(obj.inorderTraversal2(BinaryTree.integers2BinaryTree(1, null, 2)),// 
                IsIterableContainingInOrder.contains(1, 2));
    }
}