【LeetCode】 Invert Binary Tree(二叉树反转递归、非递归实现)

╰半夏微凉° 2022-07-17 04:43 133阅读 0赞

Invert a binary tree.

4
       /   \
      2     7
     / \   / \
    1   3 6   9

4
       /   \
      7     2
     / \   / \
    9   6 3   1

Trivia:  
This problem was inspired by  [this original tweet][]  by  [Max Howell][] :

Google: 90% of our engineers use the software you wrote (Homebrew), but you can’t invert a binary tree on a whiteboard so fuck off.

递归交换左右子树

\[CODE\]

**\[java\]**  [view plain][]   [copy][view plain]

1.  /\*\* 
2.   \* Definition for a binary tree node. 
3.   \* public class TreeNode \{  
4.   \*     int val; 
5.   \*     TreeNode left; 
6.   \*     TreeNode right; 
7.   \*     TreeNode(int x) \{ val = x; \} 
8.   \* \} 
9.   \*/  
10. **public** **class** Solution \{  
11.     **public** TreeNode invertTree(TreeNode root) \{  
12.         **if**(root==**null**) **return** **null**;  
13.           
14.         TreeNode temp  = root.left;  
15.         root.left = root.right;  
16.         root.right = temp;  
17.           
18.         invertTree(root.left);  
19.         invertTree(root.right);  
20.           
21.         **return** root;      
22.     \}  
23.       
24. \}

非递归算法：

1、交换根节点的左右子节点

2、交换第二层每个节点的左右子节点

....

这个与二叉树层次遍历类似，代码如下：

**\[cpp\]**  [view plain][view plain 1]   [copy][view plain 1]

[print][view plain 1] [?][view plain 1]

1.  TreeNode\* invertTree2(TreeNode\* root) \{  
2.          queue<TreeNode\*> tree\_queue;  
3.          **if** (root == NULL)  
4.              **return** root;  
5.          tree\_queue.push(root);  
6.          **while**(tree\_queue.size() > 0)\{  
7.              TreeNode \* pNode = tree\_queue.front();  
8.              tree\_queue.pop();  
9.              TreeNode \* pLeft = pNode->left;  
10.             pNode->left = pNode->right;  
11.             pNode->right = pLeft;  
12.             **if** (pNode->left)  
13.                 tree\_queue.push(pNode->left);  
14.             **if** (pNode->right)  
15.                 tree\_queue.push(pNode->right);  
16.         \}  
17.         **return** root;  
18.     \}  
19.

[this original tweet]: https://twitter.com/mxcl/status/608682016205344768
[Max Howell]: https://twitter.com/mxcl
[view plain]: http://blog.csdn.net/xudli/article/details/46554861#
[view plain 1]: http://blog.csdn.net/sunao2002002/article/details/46482559#