题目与示例
94. 二叉树的中序遍历
给定一个二叉树的根节点 root ,返回它的 中序 遍历。
示例 1:
输入:root = [1,null,2,3]
输出:[1,3,2]
示例 2:
输入:root = []
输出:[]
示例 3:
输入:root = [1]
输出:[1]
示例 4:
输入:root = [1,2]
输出:[2,1]
示例 5:
输入:root = [1,null,2]
输出:[1,2]
代码
非递归
第一步:
(1)s.addFirst(p);
(2)A.left不为空,把节点B放入栈中;
(3)B.left不为空,把节点D放入一栈中;
第二步:
(1)D.left为空,跳出里层的while循环,输出“D”;
第三步:
(1)D.right为空,跳出里层的while循环,输出B;
第四步:
(1)B.right访问到E,E进入栈内;
第五步:
(1)B.right访问到E,E进入栈内;
(2)E.left为空,跳出里层的while循环,输出“E”;
第六步:
(1)E.right为空,跳出里层的while循环,输出“A”;
第六步:
(1)A.right访问到C,C进入栈;
第六步:
(1)C.left访问到F,F进入栈;
第六步:
(1)F.left为空,跳出里层的while循环,输出“F”;
第七步:
(1)F.right为空,跳出里层的while循环,输出“C”;
第八步:
(1)C.right不为空,访问到G,G进入栈;
第九步:
(1)G.left为空,跳出里层的while循环,输出G;
(2)G.right为空,跳出里层的while循环,判断栈为空,结束;
/**
* 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) {
Stack<TreeNode> stack = new Stack<>();
List<Integer> myList = new ArrayList();
// 使用指针 记录遍历到哪个节点
TreeNode p = root;
while (p != null || !stack.isEmpty()) {
// 入栈 把当前能读到的所有左孩子 存入栈中
while (p != null) {
stack.push(p);
p = p.left;
}
if (!stack.isEmpty()) {
p = stack.pop();
myList.add(p.val);
p = p.right;
}
}
return myList;
}
}
递归
/**
* 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) {
ArrayList<Integer> myList = new ArrayList();
inOrder(root, myList);
return myList;
}
void inOrder(TreeNode node, ArrayList<Integer> myList) {
if (node == null) {
return;
}
inOrder(node.left,myList);
myList.add(node.val);
inOrder(node.right,myList);
}
}