欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

leetcode226. 翻转二叉树

程序员文章站 2022-05-18 14:36:06
...

写在前面

这道题是在阿里面试时,手撕代码的题目。刚开始用递归实现了,面试官进一步要求,能否用循环的形式实现。

  • 递归实现时,递归结束的判断条件冗余(刚开始写了两个判断条件,节点为空的时候返回,节点为叶子节点的时候返回,其实没有必要对节点是叶子节点的时候进行判断)

leetcode226. 翻转二叉树

翻转一棵二叉树。

示例:

输入:

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

输出:

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

备注:
这个问题是受到 Max Howell 的 原问题 启发的 :

谷歌:我们90%的工程师使用您编写的软件(Homebrew),但是您却无法在面试时在白板上写出翻转二叉树这道题,这太糟糕了。

完整代码

后序遍历递归形式

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    TreeNode* invertTree(TreeNode* root) {
        if(root == NULL)
      	    return root;  	

        TreeNode * Lnode = invertTree(root->left);
        TreeNode * Rnode = invertTree(root->right);
        
        root->left = Rnode;
        root->right = Lnode;	
        
        return root;
    }
};

非递归实现:中序遍历形式

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    TreeNode* invertTree(TreeNode* root) {
        if(root == NULL)
      	    return root;  	

        TreeNode* p = root;
        stack<TreeNode*> st;
        while(!st.empty() || p){
            while(p){
                st.push(p);      	
                p = p->left;
            }
            
            p = st.top();
            st.pop();
            
            //交换
            TreeNode * temp = p->right;
            p->right = p->left;
            p->left = temp;
            
            p = p->right;
            
        }
        return root;
    }
};

后续遍历非递归形式实现:
注意:什么时候节点出栈?只有当该节点的左右孩子交换完后,才出栈

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    TreeNode* invertTree(TreeNode* root) {
        if(root == NULL)
      	    return root;  	

        TreeNode* p = root, *pre;
        stack<TreeNode*> st;
        while(!st.empty() || p){
            while(p){
                st.push(p);      	
                p = p->left;
            }//p是最左面的节点
            
            p = st.top();
            
            
            if(p->right == NULL || p->right == pre){//右孩子为空,右孩子已经交换完
                TreeNode * temp = p->right;
                p->right = p->left;
                p->left = temp;
                pre = p;
                p = NULL;
                st.pop();
            }
            else{
                p = p->right;
                pre = NULL;
            }
        }
        return root;
    }
};

先序遍历非递归形式:
简单来讲:将访问节点修改成交换节点的左右子树

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    TreeNode* invertTree(TreeNode* root) {
        if(root == NULL)
      	    return root;  	

        TreeNode* p = root, *pre;
        stack<TreeNode*> st;
        while(!st.empty() || p){
            while(p){
                st.push(p);
                
                TreeNode * temp = p->right;
                p->right = p->left;
                p->left = temp;
                
                p = p->left;
            }//p是最左面的节点
            
            p = st.top();
            st.pop();
            p = p->right;      
            
            
        }
        return root;
    }
};

总结:这道题的本质:将 二叉树中先序、中序、后序遍历二叉树中访问节点的代码 改成 交换节点的左右子树的代码就OK。

相关标签: leetcode c++