旅游景区网站设计,备案网站地址,福建公司网站建设,郑州网站设计哪家公司好递归三部曲(时刻牢记) 1.确认递归函数需要的参数与返回值 一般为传入一个根节点 传入一个数组用来存放结果数组 2.确定终止条件 3.确定单层递归逻辑
递归的实现就是#xff1a;每一次递归调用都会把函数的局部变量、参数值和返回地址等压入调用栈中#xff0c;然后递归返回的… 递归三部曲(时刻牢记) 1.确认递归函数需要的参数与返回值 一般为传入一个根节点 传入一个数组用来存放结果数组 2.确定终止条件 3.确定单层递归逻辑
递归的实现就是每一次递归调用都会把函数的局部变量、参数值和返回地址等压入调用栈中然后递归返回的时候从栈顶弹出上一次递归的各项参数所以这就是递归为什么可以返回上一层位置的原因。 迭代用栈完成
二叉树的定义
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;}
}
144. 二叉树的前序遍历 根左右 递归
class Solution {public ListInteger preorderTraversal(TreeNode root) {ListInteger result new ArrayListInteger();preorder(root,result);return result;}public void preorder(TreeNode root,ListInteger result){if(root null){return;}result.add(root.val);preorder(root.left,result);preorder(root.right,result);}
} 迭代( 迭代用栈 前序遍历 中左右 进栈顺序 中右左)
class Solution {public ListInteger preorderTraversal(TreeNode root) {ListInteger result new ArrayList();if(root null){return result;}StackTreeNode stack new Stack();stack.push(root);while(!stack.isEmpty()){TreeNode node stack.pop();result.add(node.val);if(node.right ! null){stack.push(node.right);}if(node.left ! null){stack.push(node.left);}}return result;}
}
145. 二叉树的后序遍历 左右根 递归
class Solution {public ListInteger postorderTraversal(TreeNode root) {ListInteger result new ArrayList();postorder(root,result);return result;}private void postorder(TreeNode root,ListInteger result){if(root null){return;}postorder(root.left,result);postorder(root.right,result);result.add(root.val);}
} 迭代 前序遍历根左右 总是先出根结果 进栈顺序 根 右 左 出栈 根 左 右 后序遍历左右根 进栈顺序 根 左 右 出栈 根 右 左 再反转结果集 左右根
class Solution {public ListInteger postorderTraversal(TreeNode root) {ListInteger result new ArrayList();if(root null){return result;}StackTreeNode stack new Stack();stack.push(root);while(!stack.isEmpty()){TreeNode node stack.pop();if(node.left ! null){stack.push(node.left);}if(node.right ! null){stack.push(node.right);}result.add(node.val);}Collections.reverse(result);return result;}
} 94. 二叉树的中序遍历 左根右 递归
class Solution {public ListInteger inorderTraversal(TreeNode root) {ListInteger result new ArrayList();inorder(root,result);return result;}public void inorder(TreeNode root,ListInteger result){if(root null){return;}inorder(root.left,result);result.add(root.val);inorder(root.right,result);}
} 迭代( 中序遍历 左 根 右 一直遍历到最左子节点 弹出 每次弹出先添加右节点)
class Solution {public ListInteger inorderTraversal(TreeNode root) {ListInteger result new ArrayList();if(root null){return result;}StackTreeNode stack new Stack();TreeNode cur root;while(cur ! null || !stack.isEmpty()){if(cur ! null){stack.push(cur);cur cur.left;}else{TreeNode node stack.pop();result.add(node.val);cur node.right;}}return result;}
}
