反演二叉树(递归)

Question

我不知道如何输出反向二叉树。这就是我到目前为止想出的+我的伪代码。

创建二叉树

#Creating the binary tree
from binarytree import build
from binarytree import tree
   
# List of nodes 
nodes =[4, 2, 7, 1, 3, 6, 9] 
  
# Builidng the binary tree 
binary_tree = build(nodes) 
print('Binary tree from example :\n ', 
      binary_tree) 
  
# Getting list of nodes from 
# binarytree 
print('\nList from binary tree :',  
      binary_tree.values) 

输出：

​

​

伪码：

#def invert_tree(nodes, root)

#Stop recursion if tree is empty

#swap left subtree with right subtree

#invert left subtree

#invert right subtree

Answer 1

我找到了一个答案

nodes = [[4], [7, 2], [1, 3, 6, 9]]

递归

newlist1 = []
def reverse_tree(lst):
    if not lst:
        return
    newlist1.append(lst.pop(0)[::-1])
    reverse_tree(lst)

reverse_tree(nodes)

print(newlist1)

输出：

[[4], [2, 7], [9, 6, 3, 1]]

使用列表理解的

#ListComprehension
newlist2 = [x[::-1] for x in nodes]
print(newlist2)

输出：

[[4], [2, 7], [9, 6, 3, 1]]

Answer 2

Your question isn't clear;

From what I understood:

To print the nodes of an inverted tree:
    Try Level order traversal, more precisely you can use the BFS method.

或者:如果您想反转二叉树；我的方法(给定树的根节点)：

def invert_tree(self, root):
    if root:
        temp=root.left
        root.left = self.invert_tree(root.right)
        root.right = self.inver_tree(temp)
        return root

由于树中的每个节点都被访问过一次，所以时间复杂度是O(n)。

Answer 3

树节点*倒置(树节点*树){

if(tree == NULL) return NULL;

TreeNode* temp;
temp = tree->left;
tree->left = tree->right;
tree->right = temp;

Invert(tree->left);
Invert(tree->right);
return tree;

}