首页 > 试题广场 > 反转二叉树,即交换所有结点的左右子树,但不能使用递归方法。
[问答题]
反转二叉树,即交换所有结点的左右子树,但不能使用递归方法。
二叉树结构如下:
TreeNode{
     TreeNode left,right;   //左右子树
     DataType data;         //数据
}

推荐
void NonRecursive_Exchange(TreeNode *T)
{
    Stack s;
    TreeNode *p;
    if (NULL == T)
        return;
    InitStack(&s);
    Push(&s, T);
    while (!isEmpty(&s))
    {
        T = Pop(&s);
        p = T->left;
        T->left = T->right;
        T->right = p;
        if (T->right )
            Push(&s, T->right );
        if (T->left )
            Push(&s, T->left );
    }
    DestroyStack(&s);
}

编辑于 2015-01-26 14:55:21 回复(0)
public class MirrorTreeWithoutRecurrence {
    private Stack<TreeNode> stack = new Stack<TreeNode>();

    private void reverse(TreeNode ele) {
        if(ele!=null){
            TreeNode l = ele.left;
            ele.left = ele.right;
            ele.right = l;
        }

    }

    public void mirror(TreeNode root) {
        TreeNode tmp = root;
        while(!stack.isEmpty() || tmp!=null){
            while (tmp != null) {
                stack.push(tmp);
                tmp = tmp.left;
            }

            TreeNode t = stack.pop();
            tmp = t.right;
            reverse(t);
        }
    }

}

发表于 2015-01-26 11:51:32 回复(0)
// TreeNode root  = ...
// if(root == null) return ... 
Stack<TreeNode> stack = new Stack<>();
stack.push(root);
while(!stack.isEmpty()){
    TreeNode tn = stack.pop();
    TreeNode tmp = tn.left;
    tn.left = tn.right;
    tn.right= tmp
    if(tn.left != null) stack.push(tn.left);
    if(tn.right != null) stack.push(tn.right);
}
// ...

发表于 2015-01-20 23:22:05 回复(4)
public static void reverseTreeNode2(TreeNode root)
{
 if (root==null) 
 { 
  return ; 
  } 
  Queue<TreeNode> queue =new ArrayDeque<TreeNode>();
  queue.offer(root);  
 while (!queue.isEmpty()) 
 {  
  TreeNode node=queue.peek();  
  TreeNode temp=node.left; 
  node.left=node.right;  
  node.right=temp; 
  queue.poll();  
  if (node.left!=null) 
  {  
  queue.offer(node.left);
  }
  if (node.right!=null)
  {   
 queue.offer(node.right);
  } 
 } 
} 

编辑于 2015-01-22 10:41:06 回复(1)
//递归版本

TreeNode* invert_BinaryTree_Recursive(TreeNode* head){
    if(head==NULL) return NULL;
    TreeNode* node= invert_Binary_Recursive(head->left);
 head->left=invert_Binary_Recursive(head->right);
 head->right=node;
 return head;
} 


//非递归版本

TreeNode* invert_BinaryTree_NonRecursive(TreeNode* head){
    if(head==NULL) return head;
    
    stack<TreeNode*> nodes;
    nodes.push(head);
    while(!nodes.empty()){
        TreeNode* p=nodes.top();
        nodes.pop();
        swap(p->left,p->right);
        if(p->left) nodes.push(p->left);
        if(p->right) nodes.push(p->right);
    }
    return head;
}

编辑于 2015-06-12 20:13:38 回复(0)
答案:
void NonRecursive_Exchange(TreeNode* T)  
{  
 Stack s;  
 TreeNode* p;  
 if(NULL==T)  
  return;  
 InitStack(&s);  
 Push(&s,T);  
 while(!isEmpty(&s))  
 {  
  T = Pop(&s);  
  p = T->left;  
  T->left = T->right;  
  T->right = p;  
   
  if(T->right)  
   Push(&s,T->right);  
  if(T->left )  
   Push(&s,T->left );   
 }   
 DestroyStack(&s);   
}  

发表于 2015-01-29 17:16:50 回复(0)
不用递归就用栈,来模拟递归过程
发表于 2015-01-14 00:42:36 回复(0)
 class TreeNode():
    def __init__(self,val):
        self.val = val
        self.left = None
        self.right = None

def reverseTree(head):
    if head == None:
        return False 
    queue = []
    queue.append(head)
    reslist = []
    nowlist = []
    last = nlast = head
    while len(queue) != 0:
        curnode = queue.pop(0)
        nowlist.append(curnode.val)
        
        if curnode.left and curnode.right:
            curnode.left, curnode.right = curnode.right, curnode.left
            queue.append(curnode.left)
            queue.append(curnode.right)
            nlast = curnode.right
        elif curnode.left and not curnode.right:
            curnode.right = curnode.left
            curnode.left = None
            queue.append(curnode.right)
            nlast = curnode.right
        elif not curnode.left and curnode.right:
            curnode.left = curnode.right
            curnode.right = None
            queue.append(curnode.left)
            nlast = curnode.left
        if curnode == last:
            reslist.append(nowlist)
            last = nlast
            nowlist = []
    return reslist    

发表于 2018-04-10 16:20:52 回复(0)
类似于层序遍历
 TreeNode* Mirror(TreeNode *pRoot) {
		queue<TreeNode*> tree_queue;
		if (pRoot ==  NULL) return root;
		tree_queue.push(pRoot);
		while(tree_queue.size() > 0){
			TreeNode * pNode = tree_queue.front();
			tree_queue.pop();
			TreeNode *tmp = pNode->left;
			pNode->left = pNode->right;
			pNode->right = tmp;
			if (pNode->left) tree_queue.push(pNode->left);
			if (pNode->right) tree_queue.push(pNode->right);
		}
		return pRoot;
	}

编辑于 2016-05-05 16:27:24 回复(0)
/**
 * 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) {
    stack<TreeNode*> s;
    if(!root)return nullptr;
    s.push(root);
    TreeNode* tmp;
    TreeNode* tn;
    while(!s.empty())
    {
        tmp = s.top();
        s.pop();
        tn = tmp->left;
        tmp->left = tmp->right;
        tmp->right = tn;
        if(tmp->right)s.push(tmp->right);
        if(tmp->left)s.push(tmp->left);
    }
    return root;
    }
};

编辑于 2015-06-12 16:48:38 回复(2)
主要目的,是要了解递归的本质是什么!
发表于 2015-01-29 09:32:45 回复(0)
PASS
发表于 2015-01-22 19:47:07 回复(0)
这题就是“遍历所有节点”这一类型:不管是用栈还是用堆
发表于 2015-01-19 00:42:53 回复(0)