day18 leetcode-hot100-36（二叉树1）

94. 二叉树的中序遍历 - 力扣（LeetCode）

1.递归

常见算法，背下来即可

思路

中序遍历的顺序是左右根，因此遍历也是先加入左节点，再加入根节点，最后加入右节点。

具体代码

/*** 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<Integer> inorderTraversal(TreeNode root) {List<Integer> ans = new ArrayList<>();inorder(root,ans);return ans;}public void inorder(TreeNode n, List<Integer> ans){if(n==null){return;}inorder(n.left,ans);ans.add(n.val);inorder(n.right,ans);}
}

2.迭代

思路

与上面递归一模一样，只不过是显式将栈表达出来

具体代码

/*** 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<Integer> inorderTraversal(TreeNode root) {List<Integer> ans = new ArrayList<>();Deque<TreeNode> dq = new LinkedList<>();while(root!=null || !dq.isEmpty()){while(root!=null){dq.push(root);root=root.left;}root=dq.pop();ans.add(root.val);root=root.right;}return ans;}
}