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

题目描述:

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<TreeNode* > 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)(二叉树都有右子树和左子树);