leetcode|LeetCode 94. 二叉树的中序遍历


leetcode|LeetCode 94. 二叉树的中序遍历
文章图片

递归版:

class Solution { public List inorderTraversal(TreeNode root) { List res = new ArrayList<>(); if (root == null) return res; help(root, res); return res; } public void help(TreeNode root, List list) { if (root == null) return ; help(root.left, list); list.add(root.val); help(root.right, list); } }

非递归版:
思路:
用栈进行模拟,当栈非空或者root不为空的时候,就一直判断
如果root为空,说明左孩子空了,判断pop()节点,然后走右子树;否则,一直往栈里面扔左孩子
/** * Definition for a binary tree node. * public class TreeNode { *int val; *TreeNode left; *TreeNode right; *TreeNode() {} *TreeNode(int val) { this.val = val; } *TreeNode(int val, TreeNode left, TreeNode right) { *this.val = val; *this.left = left; *this.right = right; *} * } */ class Solution { public List inorderTraversal(TreeNode root) { // 非递归 List res = new ArrayList<>(); Stack stack = new Stack<>(); while (stack.size() > 0 || root != null) { if (root == null) { TreeNode node = stack.pop(); res.add(node.val); if (node.right != null) root = node.right; } else { stack.push(root); root = root.left; } } return res; } }

【leetcode|LeetCode 94. 二叉树的中序遍历】

    推荐阅读