【数据结构_11】二叉树（5）
606. 根据二叉树创建字符串
//递归过程中，把构成的String结果拼接到result里面private StringBuilder result = new StringBuilder();public String tree2str(TreeNode root) {//使用成员变量的时候，注意多组用例的情况，确保每次调用，都是从舒适化的数据开始执行result = new StringBuilder();if(root == null){return "";}tree2strHelper(root);//递归完毕之后，需要删除最外层的（）result.deleteCharAt(0);result.deleteCharAt(result.length()-1);return result.toString();}public void tree2strHelper(TreeNode root){if(root == null){return;}//把当前的根节点进行访问，访问操作就是拼接字符串result.append("(");result.append(root.val);tree2strHelper(root.left);//再递归右子树之前，判定是否左子树为空，并且右子树非空，此时就加上一组（）if(root.left == null && root.right != null){result.append("()");}tree2strHelper(root.right);//确保递归子树的过程，结果也是在“）”里面的result.append(")");}
}144. 二叉树的前序遍历（此处不用递归，用循环来写！）
思路：二叉树本身是用递归定义的，所以二叉树递归的遍历就很顺，很简单，当使用非递归的时候，意味着就需要通过循环来模拟递归的过程。找个过程我们需要借用栈来实现回溯。
递归的关键就是“回溯”，沿着调用的方向，返回到上一层，此处就是手动构造栈，模拟回溯的过程。先序遍历中，回溯发生在左子树回到根节点这个环节，之后再去递归访问右子树，因此就需要使用栈，模拟左子树递归完成，再来递归访问右子树的过程。
因此核心步骤为：
1.创建栈，根节点入栈
2.循环的把栈顶元素出栈，访问这个元素（此题中的访问，也就是把元素加到List中）
3.把右子树先入栈，再把左子树入栈（栈是后进先出的）
4.下次循环取出的栈顶就是左子树的根节点，访问，把这个根节点的右子树和左子树入栈
5.当整个左子树所有节点都访问完成，最后出栈才轮到刚才根节点右子树
/*** 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> preorderTraversal(TreeNode root) {//首先创建一个list用于存放最终得到的结果List<Integer> result = new ArrayList<>();if(root == null){return result;}//创建一个栈来帮忙完成入栈Stack<TreeNode> stack = new Stack<>();//根节点入栈stack.push(root);while(!stack.isEmpty()){TreeNode cur = new TreeNode();cur = stack.pop();result.add(cur.val);//一定要先右子树入栈再左子树入栈if(cur.right != null){stack.push(cur.right);}if(cur.left != null){stack.push(cur.left);}}return result;}
}94. 二叉树的中序遍历 - 力扣（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<>();if(root == null){return result;}Stack<TreeNode> stack = new Stack<TreeNode>();TreeNode cur = root;while(true){//1.一路往左找，只要遇到的节点不为空就入栈，此处无法访问根节点，必须找到最左侧的节点while(cur != null){stack.push(cur);cur = cur.left;}//2.上面的循环结束，意味着cur已经称为null，栈顶元素就是没有左子树的元素，就可以进行访问了if(stack.isEmpty()){//栈为空，遍历也就结束了break;}TreeNode top = stack.pop();result.add(top.val);//3.按照 左 根 右 这样的次序，上面完成了根节点的访问，接下来从右子树开始继续进行遍历cur = top.right;}return result;}
}解题思路：
中序的顺序是左、根、右
一上来不能访问根节点，需要先向左递归，必须得再左子树整个都完成了之后才能去访问根节点，根节点入栈，继续往左找，左子树的根节点也不能访问，也得入栈，继续往左找，一直重复上述过程直到遇到左子树为null的情况，然后去访问根节点（也就是把他添加到list），访问完栈顶元素，还不能继续出栈，要把栈顶元素的右子树再进行入栈，不能直接访问右子树根节点，先入栈，再找右子树的左子树，一路入栈，一路找，直到找到左子树为null的时候才能出栈访问。
步骤：
1.从根节点出发，一路入栈，直到遇到左子树为空的节点
2.出栈一个元素，访问他
3.继续从刚才整个访问元素的左子树继续往左入栈，继续找空节点。
145. 二叉树的后序遍历 - 力扣（LeetCode）
1.起手和中序一样，一路往左找，遇到元素就入栈
2.当遇到null，就可以出栈了，此时针对栈顶元素，需要进行判定
（a）如果这个栈顶元素没有右子树，那我们直接对他进行访问
（b）如果有右子树，而且这个右子树没有被访问郭，此时智能从右子树出发，继续重复上述的过程
*当回溯到根节点的时候，如何判定此时根节点的右子树是否被访问过呢？——取出结果List中的最后一个元素，看一下这个元素是不是当前根节点的右子树
/*** 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> postorderTraversal(TreeNode root) {List<Integer> result= new ArrayList<>();if(root == null){return result;}Stack<TreeNode> stack = new Stack<>();TreeNode cur = root;//记录一个Prev变量，表示上一个访问过的元素TreeNode prev = null;while(true){while(cur != null){stack.push(cur);cur = cur.left;}//当循环结束之后，取出栈顶元素if(stack.isEmpty()){break;}TreeNode top = stack.peek();if(top.right == null || top.right == prev){result.add(top.val);stack.pop();prev =top;}else{cur = top.right;}}return result;}
}