这不是我写的,对于树的学习处于初始阶段。
class Solution(object): def inorderTraversal(self, root): """ :type root: TreeNode :rtype: List[int] """ white,gray=0,1 res=[] stack=[(white,root)] while stack: color,node=stack.pop() if node is None:continue if color==white: stack.append((white,node.right)) stack.append((gray,node)) stack.append((white,node.left)) else: res.append(node.val) return res
执行用时 :32 ms, 在所有 python 提交中击败了13.08%的用户
内存消耗 :11.7 MB, 在所有 python 提交中击败了28.30%的用户
——2019.11.7
先用递归的方式写一下:
List<Integer> list = new ArrayList<>(); public List<Integer> inorderTraversal(TreeNode root) { if(root == null){ return list; }else { inorderTraversal(root.left); list.add(root.val); inorderTraversal(root.right); } return list; }
再用非递归的方式写一下:
public List<Integer> inorderTraversal(TreeNode root) { List<Integer> list = new ArrayList<>(); Stack<TreeNode> stack = new Stack<>(); if(root == null){ return list; } TreeNode node = root; while(node!=null){ stack.push(node); node = node.left; } while (!stack.isEmpty()){ TreeNode p = stack.pop(); list.add(p.val); if(p.right != null){ stack.push(p.right); p = p.right; while (p.left != null){ stack.push(p.left); p = p.left; } } } return list; }
用栈进行处理。
——2020.7.1