94. Binary Tree Inorder Traversal

不用递归来实现树的中序遍历

思路： 不熟练。非递归写法, 先一直往左遍历，并加到栈中，然后到最左子树后，开始出栈，如果有右节点，将右节点入栈

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
class Solution:
    def inorderTraversal(self, root):
        """
        :type root: TreeNode
        :rtype: List[int]
        """
        # 3 star
        # todo, 非递归写法
        rs = []
        self.inorder(root, rs)
        return rs
    def inorder(self, node, rs):
        if node:
            self.inorder(node.left, rs)
            rs.append(node.val)
            self.inorder(node.right, rs)


class Solution:
    def inorderTraversal(self, root):
        """
        :type root: TreeNode
        :rtype: List[int]
        """
        # 7 star，必须熟练掌握
        if not root:
            return []
        stack = []
        rs = []
        node = root
        while node or stack:
            if node:
                stack.append(node)
                node = node.left
            else:
                node = stack.pop()
                rs.append(node.val)
                node = node.right
        return rs

Go:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
func inorderTraversal(root *TreeNode) []int {
	if root == nil {return []int{}}
	var nums []int
	nums = inorder(root, nums)
	return nums

}


func inorder(node *TreeNode, nums []int) []int {

	if node.Left != nil {
		nums = inorder(node.Left, nums)
	}
	nums = append(nums, node.Val)
	if node.Right != nil {
		nums = inorder(node.Right, nums)
	}
	if node.Left == nil && node.Right == nil {
		return nums}
	return nums
}