1. 反转二叉树，不用递归
|
1 2 3 4 5 6 7 8 9 |
/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */ |
递归方式：
|
1 2 3 4 5 6 7 8 9 10 11 12 13 |
public class Solution { public TreeNode invertTree(TreeNode root) { if (root == null) { return null; } root.left = invertTree(root.left); root.right = invertTree(root.right); TreeNode tmp = root.left; root.left = root.right; root.right = tmp; return root; } } |
object-c实现：
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 |
/** * 翻转二叉树（又叫：二叉树的镜像） * * @param rootNode 根节点 * * @return 翻转后的树根节点（其实就是原二叉树的根节点） */ + (BinaryTreeNode *)invertBinaryTree:(BinaryTreeNode *)rootNode { if (!rootNode) { return nil; } if (!rootNode.leftNode & !rootNode.rightNode) { return rootNode; } [self invertBinaryTree:rootNode.leftNode]; [self invertBinaryTree:rootNode.rightNode]; BinaryTreeNode *tempNode = rootNode.leftNode; rootNode.leftNode = rootNode.rightNode; rootNode.rightNode = tempNode; return rootNode; } |
非递归方式：
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 |
+ (BinaryTreeNode *)invertBinaryTree:(BinaryTreeNode *)rootNode { if (!rootNode) { return nil; } if (!rootNode.leftNode & !rootNode.rightNode) { return rootNode; } NSMutableArray *queueArray = [NSMutableArray array]; //数组当成队列 [queueArray addObject:rootNode]; //压入根节点 while (queueArray.count > 0) { BinaryTreeNode *node = [queueArray firstObject]; [queueArray removeObjectAtIndex:0]; //弹出最前面的节点，仿照队列先进先出原则 BinaryTreeNode *pLeft = node.leftNode; node.leftNode = node.rightNode; node.rightNode = pLeft; -v">rightNode; node.rightNode = pLeft; ">
递归方式：
object-c实现：
非递归方式：
示例代码参考：二叉树 2. 写一个单例模式
|
