Invert Binary Tree
Question
Invert a binary tree.
Example:
4
/ \
2 7
/ \ / \
1 3 6 9
4
/ \
7 2
/ \ / \
9 6 3 1
Answer
solution:
# Definition for a binary tree node.
# class TreeNode(object):
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution(object):
def invertTree(self, root):
"""
:type root: TreeNode
:rtype: TreeNode
"""
if root is not None:
root.left, root.right = self.invertTree(root.right),self.invertTree(root.left)
return root
Knowledge:
这道题目出现在了数据挖掘的面试题里面,因此值得重视。
这道题目一开始就知道是递归,但是在思考和编程过程的时候遇到点小问题,就是递归程序写法:1.先写出整个具体操作过程以及用等号划出需要递归的部分。2.确定函数return的返回形式。3.递归位置的形式一定是"参数=函数"的形式:4.可能之前一些位置的语句也要被递归形式代替"参数=函数"。
if root is not None: root.left, root.right = root.right,root,left #若非None,则引用left,right不会出错,直接互换其左右节点 ======分别判断左右结点是不是None,再将它们各自的左右结点互换,由此发现可以递归====== return root #如果root就是None的话,直接返回本身,因为不需要翻转了
if root is not None: root.left, root.right = self.invertTree(root.right),self.invertTree(root.left) #发现需要递归的形式,与上一句语句类似,因此决定将其代替。 return root #如果root就是None的话,直接返回本身,因为不需要翻转了
Last updated
Was this helpful?