数据结构：(翻转二叉树) 若二叉树采用二叉链表作存储结构，要交换其所有分支结点的左右子树的位置，采用()遍历方法最合适

题目

若二叉树采用二叉链表作存储结构，要交换其所有分支结点的左右子树的位置，采用（）遍历方法最合适？（北京航空航天大学1999，北京工业大学2016）

A. 前序
B. 中序
C. 后序
D. 层次

---

答案

用二叉链表存储结构也就是左孩子右兄弟的存储结构。

1800题书上答案：A，C
北工大2016考研试题答案：C

评注：实际上B，D也是可以的，只不过不是很方便，因此不是“最合适”。

下面给出代码（均通过leetcode测试用例验证）

---

题解

后序遍历

做好当前结点子树内部的交换，然后交换当前结点的左右子树。

递归交换左子树

递归交换右子树

使用临时变量交换左子树与右子树

class Solution {public TreeNode invertTree(TreeNode root) {if (root != null) {invertTree(root.left); // 递归交换左子树invertTree(root.right); // 递归交换右子树TreeNode temp = root.left;root.left = root.right;root.right = temp;}return root;} }

中序遍历

递归交换 左 子树

交换左子树与右子树

（因为已经交换过了，右子树到了左边）所以仍然递归交换 左 子树

class Solution {public TreeNode invertTree(TreeNode root) {if (root != null) {invertTree(root.left); // 递归交换左子树TreeNode temp = root.left;root.left = root.right;root.right = temp;invertTree(root.left); // 递归交换左子树}return root;} }

先序遍历

交换左子树与右子树

递归交换左子树

递归交换右子树

class Solution {public TreeNode invertTree(TreeNode root) {if (root != null) {TreeNode temp = root.left;root.left = root.right;root.right = temp;invertTree(root.left); // 递归交换左子树invertTree(root.right); // 递归交换右子树}return root;} }

层次遍历

根结点入队列

出队列，交换其左右子树，将子树的根入队列

重复 2，直到队列为空

---

测试用例来源：leetcode 226.翻转二叉树

总结

以上是生活随笔为你收集整理的数据结构：(翻转二叉树) 若二叉树采用二叉链表作存储结构，要交换其所有分支结点的左右子树的位置，采用()遍历方法最合适的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。