题目描述:
思路:
- 如何翻转二叉树? 其实就是把二叉树上的每个节点的左右子节点都交换一下。
- 那么如何实现?其实就是遍历二叉树的所有节点,然后对每一个节点实施【交换子节点】的 *** 作
代码实现:
// 如何翻转二叉树: 其实就是把二叉树上的每个节点的左右子节点都交换一下, // 那么如何实现呢? 那就是遍历二叉树的所有节点,并且对每个节点实施交换子节点的 *** 作 class Solution { public TreeNode invertTree(TreeNode root) { // 出口 if (root == null){ return null; } // 前序遍历的位置 // 对于root节点,需要交换它的左右子节点 TreeNode tmp = root.left; root.left = root.right; root.right = tmp; // 递归框架,遍历并交换所有子树节点 invertTree(root.left); invertTree(root.right); // 返回一个root,其实就是最后返回一颗二叉树 return root; } }
总结:
二叉树算法有两大类别:
-
分解子问题类型
在于明确递归函数的定义,然后利用这个定义即可 -
二叉树遍历框架就是这几行代码,可以遍历二叉树的所有节点:
关键在于自己判断算法应该使用哪一种遍历框架!!!
// 二叉树遍历框架 void traverse(TreeNode root) { // 前序遍历 traverse(root.left) // 中序遍历 traverse(root.right) // 后序遍历 }
欢迎分享,转载请注明来源:内存溢出
评论列表(0条)