You've successfully subscribed to The Daily Awesome
Great! Next, complete checkout for full access to The Daily Awesome
Welcome back! You've successfully signed in.
Success! Your account is fully activated, you now have access to all content.
Success! Your billing info is updated.
Billing info update failed.

094. 二叉树的中序遍历 - Binary Tree Inorder Traversal

. 1 min read

094. 二叉树的中序遍历 - Binary Tree Inorder Traversal

【中序遍历-递归】 【中序遍历-迭代】

给定一个二叉树,返回它的中序遍历。

Example:

输入: [1,null,2,3]
   1
    \
     2
    /
   3

输出: [1,3,2]

Solutions

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

Solution 【中序遍历-递归】 ( 0ms)

class Solution {
    List<Integer> result = new LinkedList<>();
    public List<Integer> inorderTraversal(TreeNode root) {
        if (root != null){	//相比 if (root == null) return result; 会快1ms
            inorderTraversal(root.left);
        	result.add(root.val);
        	inorderTraversal(root.right);
        }
        return result;
    }

}

Solution 【中序遍历-迭代】 ( 2ms)

class Solution {
    
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> result = new LinkedList<>();
  		Stack<TreeNode> stack = new Stack<TreeNode>();
  		TreeNode current = root;
  		while (current != null || !stack.isEmpty()) {
  			while (current != null) {
  				stack.push(current);
  				current = current.left;
  			}
  			if (!stack.isEmpty()) {
  				current = stack.pop();
  				result.add(current.val);
  				current = current.right;
  			}
  		}
        return result;
    }
}

Notes