【LeetCode每天一题】Binary Tree Inorder Traversal(二叉树的中序遍历)

佚名 6年前 (2019-05-08) 随笔 644人围观抢沙发百度已收录

Given a binary tree, return the inorder traversal of its nodes' values.

Example:

SRE实战互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。

Input: [1,null,2,3]
   1
    \
     2
    /
   3

Output: [1,3,2]

Follow up: Recursive solution is trivial, could you do it iteratively?

思路

　　这道题考察的是二叉树的中序遍历，中序遍历的解法有两种，一种是使用递归，一种是使用循环来解决。下面附上两种解法的代码。

解决代码

　　递归解决代码　

 1 # Definition for a binary tree node.
 2 # class TreeNode(object):
 3 # def __init__(self, x):
 4 # self.val = x
 5 # self.left = None
 6 # self.right = None
 7 
 8 class Solution(object):  9     def inorderTraversal(self, root): 10         """
11  :type root: TreeNode 12  :rtype: List[int] 13         """
14         if not root: # 空节点直接返回 15             return [] 16         res  =[] 17  self.indorder(root, res) # 中序遍历 18         return res 19     
20     def indorder(self, root, res): # 中序遍历函数 21         if not root: 22             return
23         
24  self.indorder(root.left, res) 25  res.append(root.val) 26         self.indorder(root.right, res)

　　循环解决代码(循环主要是使用栈来解决)

 1 # Definition for a binary tree node.
 2 # class TreeNode(object):
 3 # def __init__(self, x):
 4 # self.val = x
 5 # self.left = None
 6 # self.right = None
 7 
 8 class Solution(object):  9     def inorderTraversal(self, root):   
14         if not root: 15             return [] 16         res = [] # 记录结果列表 17         stack = [] 18         while stack or root: # 循环条件 19             if root: # 中序遍历，需要先将左边节点遍历完毕。 20  stack.append(root) 21                 root = root.left 22             else: # 意味左节点为空，这时进行弹出。并遍历弹出节点的右子树。 23                 root = stack.pop() 24  res.append(root.val) 25                 root = root.right 26         return res