94.Binary-Tree-Inorder-Traversal.md

94. Binary Tree Inorder Traversal

---

题目地址

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

题目描述

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

Example:
Input: [1,null,2,3]
   1
    \
     2
    /
   3

Output: [1,3,2]
Follow up: Recursive solution is trivial, could you do it iteratively?

代码

Approach #1 Recursive Approach

Complexity Analysis

• Time complexity : O(n)
• Space complexity : The worst case space required is O(n), and in the average case it's O(logn) where n is number of nodes.

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

Approach #2 Iterating method using stack

Complexity Analysis

• Time complexity : O(n)
• Space complexity : O(n)

1. Push the left node first
2. Pop and visit the value
3. Try to move to the right node

class Solution {
  pulic List<Integer> inorderTraversal(TreeNode root) {
    List<Integer> res = new ArrayList<>();
    Stack<TreeNode> stack = new Stack<>();
    TreeNode curr = root;
    while (curr != null || !stack.isEmpty()) {
      // 1. Push the left node first
      while (curr != null) {
        stack.push(curr);
        curr = curr.left;
      }
      // 2. Pop and visit the value
      curr = stack.pop();
      res.add(curr.val);
      // 3. Try to move to the right node
      curr = curr.right;
    }
    
    return res;
  }
}

Approach #3 Morris Traversal

Step 1: Initialize current as root

Step 2: While current is not NULL,

Complexity Analysis

• Time complexity : O(n)
• Space complexity : O(n)

If current does not have left child

    a. Add current’s value

    b. Go to the right, i.e., current = current.right

Else

    a. In current's left subtree, make current the right child of the rightmost node

    b. Go to this left child, i.e., current = current.left

class Solution {
  public List<Integer> inorder inorderTraversal(TreeNode root) {
    List<Integer> res = new ArrayList<>();
    TreeNode curr = root;
    TreeNode pre;
    while (curr != null) {
      if (curr.left == null) {
        res.add(curr.val);
        curr = curr.right;
      } else {
        pre = curr.left;
        while (pre.right != null) {
          pre = pre.right;
        }
        pre.right = curr;
        TreeNode temp = curr;
        curr = curr.left;
        
        temp.left = null;
      }
    }
    return res;
  }
}

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