代码随想录Day14：二叉树Part1

二叉树遍历：

1.递归遍历：

  前序： 中左右

public class Solution
{
    public IList<int> PreorderTraversal(TreeNode root)
    {
        List<int> list = new List<int>();
        Rever(root, list);
        return list;
    }
 
    public void Rever(TreeNode root,List<int> list)
    {
        if (root == null)
            return;
 
        list.Add(root.val);
        Rever(root.left,list);
        Rever(root.right, list);
    }
}

中序：左中右

public class Solution {
    public IList<int> InorderTraversal(TreeNode root) {
 
                List<int> list = new List<int>();
        midRever(root, list);
        return list;
    }
        public void midRever(TreeNode root, List<int> list)
    {
        if (root == null)
            return;
        midRever(root.left, list);
        list.Add(root.val);
        midRever(root.right,list); 
    }
}

后序 ：左右中

public class Solution {
    public IList<int> PostorderTraversal(TreeNode root) {
 
                List<int> list = new List<int>();
        lastRever(root, list);
        return list;
    }
        public void lastRever(TreeNode root, List<int> list)
    {
        if (root == null)
            return;
        lastRever(root.left,list);
        lastRever(root.right,list);
        list.Add(root.val);
    }
}

2.迭代遍历 

前序：

public class Solution
{
    public IList<int> PreorderTraversal(TreeNode root)
    {
        Stack<TreeNode> stack = new Stack<TreeNode>();
        List<int> list = new List<int>();
        stack.Push(root);
        while (stack.Count > 0) 
        {
            TreeNode node = stack.Pop();
            if (node!=null)
            {
                list.Add(node.val);
            }
            else
            {
                continue;
 
            }
            stack.Push(node.right);
            stack.Push(node.left);
        }
        return list;
 
    }
 
}