三个要点:
前序遍历:中左右
中序遍历:左中右
后序遍历:左右中
- class Solution(object):
- def preorderTraversal(self, root):
- """
- :type root: TreeNode
- :rtype: List[int]
- """
- result =[]
- def Traversal(root):
- if root == None:
- return
- result.append(root.val)
- Traversal(root.left)
- Traversal(root.right)
-
- Traversal(root)
- return result
- class Solution(object):
- def postorderTraversal(self, root):
- """
- :type root: TreeNode
- :rtype: List[int]
- """
- result = []
-
- def traversal(root):
- if root == None:
- return
- traversal(root.left) # 左
- traversal(root.right) # 右
- result.append(root.val) # 后序
-
- traversal(root)
- return result
中右左-反转变成左右中
- var postorderTraversal = function(root) {
- // 左右中
- let result = []
- let stack = []
- stack.push(root)
- while(stack.length){
- let node = stack.pop()
- if(node){
- result.push(node.val)
- if(node.left){
- stack.push(node.left)
- }
- if(node.right){
- stack.push(node.right)
- }
- }
- }
- return result.reverse()
- };
- class Solution(object):
- def inorderTraversal(self, root):
- """
- :type root: TreeNode
- :rtype: List[int]
- """
- #中序遍历:左中右
- result = []
- def traversal(root):
- if root is None:
- return
- traversal(root.left)
- result.append(root.val)
- traversal(root.right)
-
- traversal(root)
- return result
递归法
- var inorderTraversal = function(root) {
- let result =[]
- const traversal = function(node){
- // 左中右
- if(node === null){
- return
- }
- if(node.left){
- traversal(node.left)
- }
- result.push(node.val)
- if(node.right){
- traversal(node.right)
- }
- return result
- }
- if(root === null){
- return []
- }
- return traversal(root)
-
- };
迭代法
- var inorderTraversal = function(root) {
- let result = []
- let stack = []
- let cur = root
- while(stack.length||cur){
- if(cur){
- stack.push(cur)
- cur = cur.left
- }else{
- cur = stack.pop()
- result.push(cur.val)
- cur = cur.right
- }
- }
- return result
- };
题目链接/文章讲解/视频讲解:代码随想录
前序改为后序只需要三行代码:
中左右->中右左->左右中
访问节点/处理节点
- #前序
- class Solution(object):
- def preorderTraversal(self, root):
- """
- :type root: TreeNode
- :rtype: List[int]
- """
- stack = []
- result = []
- if root is not None:
- stack.append(root)
- while stack:
- node = stack.pop()
- if node is not None:
- if node.right is not None:
- stack.append(node.right)
- if node.left is not None:
- stack.append(node.left)
- stack.append(node)
- stack.append(None)
- else:
- node = stack.pop()
- result.append(node.val)
- return result
- #后序
- class Solution(object):
- def postorderTraversal(self, root):
- """
- :type root: TreeNode
- :rtype: List[int]
- """
- result = []
- stack = []
- if root:
- stack.append(root)
- while stack:
- node = stack.pop()
- if node != None:
-
- if node.left:
- stack.append(node.left)
- if node.right:
- stack.append(node.right)
- stack.append(node)
- stack.append(None)
- else:
- node = stack.pop()
- result.append(node.val)
- return reversed(result)
- # Definition for a binary tree node.
- # class TreeNode(object):
- # def __init__(self, val=0, left=None, right=None):
- # self.val = val
- # self.left = left
- # self.right = right
- class Solution(object):
- #中序遍历
- def inorderTraversal(self, root):
- """
- :type root: TreeNode
- :rtype: List[int]
- """
- #中序遍历:左中右
- result = []
- stack = []
- if root:
- stack.append(root)
- while stack:
- node = stack.pop()
- if node is not None:
- if node.right is not None:
- stack.append(node.right)
-
- stack.append(node)
- stack.append(None)
-
- if node.left is not None:
- stack.append(node.left)
- else:
- node = stack.pop()
- result.append(node.val)
- return result
如何标记呢,就是要处理的节点放入栈之后,紧接着放入一个空指针作为标记。 这种方法也可以叫做标记法。