leetcode226. 翻转二叉树
程序员文章站
2022-05-18 14:18:50
...
思路:先序、后序、中序遍历,然后每次都进行左右子树的交换。
遇到的坑:中序遍历时,先遍历一个树,在交换左右子树,再遍历时,其实还这个这个树(大家可以细品)
先序递归:
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public TreeNode invertTree(TreeNode root) {
if(root==null)
return root;
//三部曲交换左右子树
TreeNode p=root.left;
root.left=root.right;
root.right=p;
//左右子树递归
root.right = invertTree(root.right);
root.left = invertTree(root.left);
return root;
}
}
事后有发现一个不错的代码,挂上来,供大家参考下
class Solution {
// 先序遍历--从顶向下交换
public TreeNode invertTree(TreeNode root) {
if (root == null) return null;
// 保存右子树
TreeNode rightTree = root.right;
// 交换左右子树的位置
root.right = invertTree(root.left);
root.left = invertTree(rightTree);
return root;
}
}
中序遍历:
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public TreeNode invertTree(TreeNode root) {
if(root==null)
return root;
root.right = invertTree(root.right);
//三部曲交换左右子树
TreeNode p=root.left;
root.left=root.right;
root.right=p;
//左右子树递归
root.right = invertTree(root.right);
return root;
}
}
后序遍历:
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public TreeNode invertTree(TreeNode root) {
if(root==null)
return root;
root.right = invertTree(root.right);
root.left = invertTree(root.left);
//三部曲交换左右子树
TreeNode p=root.left;
root.left=root.right;
root.right=p;
//左右子树递归
return root;
}
}
上一篇: C#集合遍历时删除和增加元素的方法
下一篇: 浅谈自动采集程序及入库