2023网页游戏大全_制作公司网站教程_广告投放平台系统_怎么在百度上发广告

二叉树前中后遍历（迭代遍历）

前序遍历

public List<Integer> preorderTraversal(TreeNode root) {List<Integer> res = new ArrayList<>();if (root == null) return res;Stack<TreeNode> stack = new Stack<>();stack.push(root);while (!stack.isEmpty()) {TreeNode node = stack.pop();res.add(node.val);//先右后左if (node.right != null) stack.push(node.right);if (node.left != null) stack.push(node.left);}return res;
}

中序遍历

public List<Integer> inorderTraversal(TreeNode root) {List<Integer> res = new ArrayList<>();if (root == null) return res;Stack<TreeNode> stack = new Stack<>();TreeNode cur = root;while (cur != null || !stack.isEmpty()) {//找最左边的节点while (cur != null) {stack.push(cur);cur = cur.left;}//弹出栈顶，访问cur = stack.pop();res.add(cur.val);//找右节点cur = cur.right;}return res;
}

后序遍历

//后序遍历相当于先序遍历的逆序
public List<Integer> postorderTraversal(TreeNode root) {List<Integer> res = new ArrayList<>();if (root == null) return res;Stack<TreeNode> stack = new Stack<>();stack.push(root);while (!stack.isEmpty()) {TreeNode cur = stack.pop();res.add(cur.val);if (cur.left != null) stack.push(cur.left);if (cur.right != null) stack.push(cur.right);}// 反转return res.reversed();
}