本文共 1727 字，大约阅读时间需要 5 分钟。

c/c++ leetcode 226. 翻转二叉树

题目描述:

难度简单537

翻转一棵二叉树。

示例：

输入：

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

输出：

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

解法一:递归

//需要注意的是子树只有一个节点时也需要翻转 ，前序和后序没有问题,只是中序需要点额外的操作,如果翻转节点后就访问的是左子树而不是右子树

TreeNode* invertTree(TreeNode* root) {        if (!root) return NULL;               invertTree(root -> left);        //中序,前序,后序都可以        if (!(root -> left == NULL && root -> right == NULL)) {            TreeNode* temp = root -> left;            root ->  left= root -> right;            root -> right  = temp;            invertTree(root -> left)        }        return root;    }};

时空复杂度分析:

时间复杂度:要遍历整个二叉树为O(N);N为二叉树节点的个数;

空间复杂度:最坏复杂度为O(N)(二叉树都只有左子树或者右子树);平均空间复杂度为O(logN)(二叉树都有右子树和左子树);

解法二.使用stack容器中序遍历迭代

需要注意的是

class Solution {public:    TreeNode* invertTree(TreeNode* root) {        if (!root) return NULL;        stack
   
     temp;        TreeNode * currNode = root;        while (!temp.empty() || currNode) {               //THIS:            while (currNode) {                temp.push(currNode);                currNode = currNode -> left;            }            currNode = temp.top();            temp.pop();                        if (!(!currNode -> left && !currNode ->right )){                TreeNode* temp = currNode -> left;                currNode->  left= currNode -> right;                currNode -> right  = temp;                currNode = currNode -> left;                continue;//不让程序执行currNode = currNode -> right;这行代码            }            			 //这行代码不能省略,要把currNode 置为NULL,在不进入if语句执行这条语句             currNode = currNode -> right;        }                return root;    }};
   

时空复杂度分析:

时间复杂度:要遍历整个二叉树为O(N);N为二叉树节点的个数;

空间复杂度:最坏复杂度为O(N)(二叉树都只有左子树或者右子树);平均空间复杂度为O(logN)(二叉树都有右子树和左子树);

转载地址：http://idyki.baihongyu.com/