树的三种遍历

实现的代码都不繁琐，相信聪明如你，一定可以理解。所以就不啰嗦了，直接上代码吧。
PS：思路来源–>https://www.cnblogs.com/qjmnong/p/9135386.html

前序遍历–>传送门

（1）递归法

class Solution {
    List<Integer> list = new ArrayList<Integer>();
    public List<Integer> preorderTraversal(TreeNode root) {
        if (root != null) {
            list.add(root.val);
            if (root.left != null) {
                preorderTraversal(root.left);
            }
            if (root.right != null) {
                preorderTraversal(root.right);
            }
        }
        return list;
    }
}

（2）迭代法（借助栈）

class Solution {
    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> list = new ArrayList<Integer>();
        // 借助栈数据结构用于树结点的回溯
        Stack<TreeNode> stack = new Stack<TreeNode>();
        if (root != null) 
        {
            stack.push(root);
            while (!stack.isEmpty())
            {
                root = stack.pop();
                list.add(root.val);
                if (root.right != null) 
                {
                    stack.push(root.right);
                }
                if (root.left != null) 
                {
                    stack.push(root.left);
                }
            }
        }
        return list;
    }
}

中序遍历–>传送门

（1）递归法

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

（2）迭代法

class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> list = new ArrayList<Integer>();
        Stack<TreeNode> stack = new Stack<TreeNode>();
        if (root != null)
        {
            stack.push(root);
            while (!stack.isEmpty())
            {
                // 保证遍历顺序：左-根-右
                while (root.left != null)
                {
                    stack.push(root.left);
                    root = root.left;
                }
                // 处理右结点
                while (!stack.isEmpty())
                {
                    root = stack.pop();
                    list.add(root.val);
                    if (root.right != null)
                    {
                        stack.push(root.right);
                        root = root.right;
                        break;
                    }
                }
            }
        }
        return list;
    }
}

后序遍历–>传送门

（1）递归法

class Solution {
    List<Integer> list = new ArrayList<Integer>();
    public List<Integer> postorderTraversal(TreeNode root) {
        if (root != null)
        {
            if (root.left != null)
            {
                postorderTraversal(root.left);
            }
            if (root.right != null)
            {
                postorderTraversal(root.right);
            }   
            list.add(root.val);
        }
        return list;
    }
}

（2）迭代法

// 该方法十分巧妙。逆序左-右-根的遍历顺序，以根-右-左开始遍历；然后借助List的末尾添加方法，负负得正，变为左-右-根的遍历顺序。
class Solution {
    public List<Integer> postorderTraversal(TreeNode root) {
        List<Integer> list = new ArrayList<Integer>();
        Stack<TreeNode> stack = new Stack<TreeNode>();
        if (root != null)
        {
            stack.push(root);
            while (!stack.isEmpty())
            {
                root = stack.pop();
                if (root.left != null)
                {
                    stack.push(root.left);
                }
                if (root.right != null)
                {
                    stack.push(root.right);
                }
                list.add(0, root.val);
            }
        }
        return list;
    }
}