LeetCode算法题-Invert Binary Tree
这是悦乐书的第194次更新,第199篇原创
01 看题和准备
今天介绍的是LeetCode算法题中Easy级别的第55题(顺位题号是226)。反转二叉树。例如:
输入:
4
/ \
2 7
/ \ / \
1 3 6 9
输出:
4
/ \
7 2
/ \ / \
9 6 3 1
本次解题使用的开发工具是eclipse,jdk使用的版本是1.8,环境是win7 64位系统,使用Java语言编写和测试。
02 第一种解法
二叉树的任意一个节点进行反转操作时,当前节点还是当前节点,当前节点的左子节点变成右子节点,当前节点的右子节点变成左子节点。也就是下面的三行核心代码:
TreeNode temp = root.left;
root.left = root.right;
root.right = temp;
如果从根节点开始,那么先把根节点的左右子节点互换,然后利用递归,再将已经互换了的左右子节点他们自身的左右子节点进行互换,最后返回root。
public TreeNode invertTree(TreeNode root) {
if (root == null || (root.left == null && root.right == null)) {
return root;
}
TreeNode temp = root.left;
root.left = root.right;
root.right = temp;
root.left = invertTree(root.left);
root.right = invertTree(root.right);
return root;
}
03 第二种解法
此解法比上面的第一种解法精简了些,直接将上面核心代码进行套用,将root的左子节点取出存入tmp,再将root的左子节点指向递归后的root的右子节点,再将root的右子节点指向递归后的tmp,最后返回root即可。
public TreeNode invertTree2(TreeNode root) {
if (root == null || (root.left == null && root.right == null)) {
return root;
}
TreeNode tmp = root.left;
root.left = invertTree2(root.right);
root.right = invertTree2(tmp);
return root;
}
04 第三种解法
利用队列,借助其先进先出的特性。在进行循环进队列、出队列的操作时,核心代码还是最开始那三行代码,进行左右子节点互换。
public TreeNode invertTree3(TreeNode root) {
TreeNode r = root;
Queue<TreeNode> q = new LinkedList<TreeNode>();
if (root != null) {
q.add(root);
}
while (!q.isEmpty()) {
TreeNode curr = q.remove();
TreeNode temp = curr.left;
curr.left = curr.right;
curr.right = temp;
if (curr.left != null) {
q.add(curr.left);
}
if (curr.right != null) {
q.add(curr.right);
}
}
return r;
}
05 小结
算法专题目前已连续日更超过一个月,算法题文章55+篇,