递归

• 算法
  • 递归

public void preorder(TreeNode root, List<Integer> list) {
    if (root != null) {
        list.add(root.val);
        preorder(root.left, list);
        preorder(root.right, list);
    }
}
public void inorder(TreeNode root, List<Integer> list) {
    if (root != null) {
        inorder(root.left, list);
        list.add(root.val);
        inorder(root.right, list);
    }
}
public void postorder(TreeNode root, List<Integer> list) {
    if (root != null) {
        postorder(root.left, list);
        postorder(root.right, list);
        list.add(root.val);
    }
}

前序遍历迭代

• 前序遍历迭代
  • 算法1
    • 1.根节点入栈
    • 2.当栈非空时，栈顶出栈，把出栈的节点值添加到 list 结尾，然后依次再入栈其右子节点和左子节点
    • ps：因为前序遍历要左子节点在右子节点前面，所以先入栈右子节点，后入栈左子节点
  • 算法2
    • 1.辅助变量 curr 初始化为根节点
    • 2.当 curr != null 时，就保存这个节点值到 list 中，然后将其入栈并置 curr 为它自己的左子节点
    • 3.当 curr == null 时，说明已经遍历到二叉树的左下节点了，这时前序遍历应该遍历右子树了，首先 pop 出已经遍历保存过的父节点，然后置 curr 为 pop 出的父节点的右子节点
  • 算法3
    • 和算法2的区别：父节点遍历到之后直接保存下来不再入栈，随后入栈其右子节点，这样出栈的时候也不必再置为其右子节点

    public void preorder(TreeNode root, ArrayList<Integer> list) {
        Stack<TreeNode> stack = new Stack<>();
        stack.push(root);
        while (!stack.isEmpty()) {
            TreeNode curr = stack.pop();
            list.add(curr.val);
            if (curr.right != null) {
                stack.push(curr.right);
            }
            if (curr.left != null) {
                stack.push(curr.left);
            }
        }
    }
    public void preorder(TreeNode root, ArrayList<Integer> list) {
        Stack<TreeNode> stack = new Stack<>();
        TreeNode curr = root;
        while (!stack.isEmpty() || curr != null) {
            if (curr != null) {
                list.add(curr.val);
                stack.push(curr);
                curr = curr.left;
            } else {
                curr = stack.pop();
                curr = curr.right;
            }
        }
    }
    public void preorder(TreeNode root, ArrayList<Integer> list) {
        Stack<TreeNode> stack = new Stack<>();
        TreeNode curr = root;
        while (!stack.isEmpty() || curr != null) {
            if (curr != null) {
                list.add(curr.val);
                if (curr.right != null) {
                    stack.push(curr.right);
                }
                curr = curr.left;
            } else {
                curr = stack.pop();
            }
        }
    }

中序遍历迭代

• 中序遍历迭代
  • 算法1
    • 1.辅助变量 curr 初始化 root
    • 3.当栈非空或 curr 非 null 时，循环
      • 3.1 curr != null 时，说明还有左子节点存在，将 curr 入栈，并且将 curr 置为它自己的左子节点（和前序遍历的区别在于这里遍历到先不保存到 list 中，出栈的时候再将其保存到 list 中）
      • 3.2 curr == null 时，说明到二叉树左下的节点了，这时栈顶的父节点出栈赋值给 curr ，并保存节点值到 list ，将 curr 置为栈顶节点的右子节点继续循环
  • 算法2
    • 算法1的另一种形式

    public void inorder(TreeNode root, ArrayList<Integer> list) {
        Stack<TreeNode> stack = new Stack<>();
        TreeNode curr = root;
        while (!stack.isEmpty() || curr != null) {
            if (curr != null) {
                stack.push(curr);
                curr = curr.left;
            } else {
                curr = stack.pop();
                list.add(curr.val);
                curr = curr.right;
            }
        }
    }

    public void inorder(TreeNode root, ArrayList<Integer> list) {
        Stack<TreeNode> stack = new Stack<>();
        TreeNode curr = root;
        while (!stack.isEmpty() || curr != null) {
            while (curr != null) {
                stack.push(curr);
                curr = curr.left;
            } 
            curr = stack.pop();
            list.add(curr.val);
            curr = curr.right;
        }
    }

后序遍历迭代

• 后序遍历迭代
  • 三种算法分别对应前序遍历的反操作：
    • 前序遍历从尾部添加元素，后序遍历从头部添加元素
    • 前序遍历去左子树，后序遍历去右子树

    public void postorder(TreeNode root, ArrayList<Integer> list) {
        Stack<TreeNode> stack = new Stack<>();
        stack.push(root);
        while (!stack.isEmpty()) {
            TreeNode curr = stack.pop();
            list.add(0, curr.val);
            if(curr.left != null) {
              stack.push(curr.left);
            }
            if(curr.right != null) {
               stack.push(curr.right); 
            }
        }
    }
    public void postorder(TreeNode root, List<Integer> list) {
        Stack<TreeNode> stack = new Stack<>();
        TreeNode curr = root;
        while (!stack.isEmpty() || curr != null) {
            if (curr != null) {
                stack.push(curr);
                list.add(0, curr.val);
                curr = curr.right;
            } else {
                curr = stack.pop();
                curr = curr.left;
            }
        }
    }
    public void postorder(TreeNode root, List<Integer> list) {
        Stack<TreeNode> stack = new Stack<>();
        TreeNode curr = root;
        while (!stack.isEmpty() || curr != null) {
            if (curr != null) {
                list.add(0, curr.val);
                if (curr.left != null) {
                    stack.push(curr.left);
                }
                curr = curr.right;
            } else {
                curr = stack.pop();
            }
        }
    }