【Check 45】2024-04-07 - 94. 二叉树的中序遍历

[larscheng]

94. 二叉树的中序遍历

[larscheng]

思路

• 递归

  代码

class Solution { //O(n)/O(n) //递归中序遍历 public List inorderTraversal(TreeNode root) { List res = new ArrayList<>(); inorder(root, res); return res; }

private void inorder(TreeNode root, List<Integer> res) {
    if (root == null) {
        return;
    }
    inorder(root.left, res);
    res.add(root.val);
    inorder(root.right, res);
}

}

```java
    //左节点+根节点+右节点
    //addall 空间复杂度高O(n^2)
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        if (root == null) {
            return res;
        }
        res.addAll(inorderTraversal(root.left));
        res.add(root.val);
        res.addAll(inorderTraversal(root.right));
        return res;
    }

复杂度

• 时间复杂度：O(n)
• 空间复杂度：O(n)

[larscheng]

思路

• 迭代实现，不使用递归，手动记录栈结构，栈中只存每个节点的左子节点

  代码

  class Solution3 {
      //O(n)/O(n)
      //迭代中序遍历，手动记录栈
      public List<Integer> inorderTraversal(TreeNode root) {
          List<Integer> res = new ArrayList<>();
          Stack<TreeNode> stack = new Stack<>();
  
          while (root != null || !stack.isEmpty()) {
              while (root != null) {
                  stack.push(root);
                  root = root.left;
              }
              //取出栈中的左子树
              root = stack.pop();
              res.add(root.val);
              root = root.right;
          }
          return res;
      }
  
  }

复杂度

• 时间复杂度：O(n)
• 空间复杂度：O(n)

[larscheng]

思路

• 颜色标记法，
  1. 根节点先入栈，标记位白色
  2. 弹出栈顶元素和其对应的颜色标记，跳过空值， a. 如果为白色：将栈顶元素按照右子树（白色），当前节点（灰色），左子树（白色）的顺序入栈 b. 如果为灰色：记录节点值
  3. 循环操作2

这种栈结构中，最先出栈的必定是左子树，最先记录的节点必定是左叶子节点

代码

class Solution {

    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        Stack<Object> stack = new Stack<>();
        if (root==null){
            return res;
        }
        stack.push("white");
        stack.push(root);

        while (!stack.isEmpty()){
            TreeNode node = (TreeNode) stack.pop();
            String color = (String) stack.pop();
            if (node == null){
                continue;
            }
            if (color.equals("white")){
                stack.push("white");
                stack.push(node.right);
                stack.push("gray");
                stack.push(node);
                stack.push("white");
                stack.push(node.left);
            }else {
                res.add(node.val);
            }
        }
        return res;
    }

}

复杂度

• 时间复杂度：O(n)
• 空间复杂度：O(n)