首页 > 试题广场 >

反转二叉树，即交换所有结点的左右子树，但不能使用递归方法。

[问答题]

反转二叉树，即交换所有结点的左右子树，但不能使用递归方法。
二叉树结构如下：

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)

__getattr__

// 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)

Monk

//递归版本

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)

牛客-007

答案：

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)

大漠苍鹰

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)

SunnuS

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)

罗那耳朵21

/**
 * 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)

writezen

主要目的，是要了解递归的本质是什么！

发表于 2015-01-29 09:32:45 回复(0)

Lucifer2603

PASS

发表于 2015-01-22 19:47:07 回复(0)

牛客979292号

这题就是“遍历所有节点”这一类型：不管是用栈还是用堆

发表于 2015-01-19 00:42:53 回复(0)

提交观点

问题信息

树递归

上传者：小牧魔法袋

难度：

13条回答 27收藏 40131浏览

反转二叉树，即交换所有结点的左右子树，但不能使用递归方法。

问题信息

热门推荐

相关试题