94. Binary Tree Inorder Traversal（中序遍历二叉树）

迷南。 2022-07-14 06:07 136阅读 0赞

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]`.

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

题目大意：中序遍历二叉树。

解题思路：

解法一，递归。代码如下：（1ms，beats 35.43%）

/**
     * Definition for a binary tree node.
     * public class TreeNode {
     *     int val;
     *     TreeNode left;
     *     TreeNode right;
     *     TreeNode(int x) { val = x; }
     * }
     */
    public class Solution {
        List<Integer> list = new ArrayList<Integer>();
    
    	public List<Integer> inorderTraversal(TreeNode root) {
    		inorder(root);
    		return list;
    	}
    	
    	public void inorder(TreeNode root){
    		if(root==null)
    			return;
    		inorder(root.left);
    		list.add(root.val);
    		inorder(root.right);
    	}
    }

解法二，循环。代码如下： （1ms，beats 35.43%）

/**
     * 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<Integer> inorderTraversal(TreeNode root) {
    		List<Integer> list = new ArrayList<Integer>();
    		TreeNode[] stack = new TreeNode[1000];
    		int index = 0;
    		TreeNode p = root;
    		while (p != null || index > 0) {
    			if(p!=null){
    				stack[index++] = p;
    				p = p.left;
    			}else{
    				p = stack[--index];
    				list.add(p.val);
    				p = p.right;
    			}
    		}
    		return list;
    	}
    	
    }