LeetCode——二叉树的中序遍历_二叉树的中序遍历leetcode

题目：

解题思路：
对一个二叉树进行中序遍历，本质上就是对二叉树进行深度优先搜索。以上图中的树为例我们取出根节点首先判断其是否有左子树，如果有左子树则对其左子树进行搜索，搜索完左子树访问根节点然后再搜索这一节点的右子树。左子树和右子树的搜索过程与上述相同。
根据解题思路不难发现上述的过程就是一个递归的过程因此我们可以用递归的方式来对其进行求解，代码如下：

/**
 * 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> result = new ArrayList<Integer>();      
        if(root==null){
            return result;
        }     
        result.addAll(inorderTraversal(root.left));
        result.add(root.val);
        result.addAll(inorderTraversal(root.right));
        return result;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

上述方式是用递归的方式解题，而一般来说递归的方法也可以转变成迭代的方法。
首先我们定义一个栈的结构，用来存储结点，然后根据深度优先搜索的思想，从根节点开始一直找到树的最左边一个节点，然后从栈中取出一个节点访问其数据，再指向他的右子树节点接着按照上述方式对其右子树进行遍历直到遍历完所有节点。代码如下所示：

/**
 * 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> result = new ArrayList<>();
        if(root==null){
            return result;
        }
        while(!stack.isEmpty()||root!=null){
            while(root!=null){
                stack.push(root);
                root = root.left;
            }
            TreeNode node = stack.pop();
            result.add(node.val);
            root = node.right;
        }
        return result;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34